Submission #00204

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long
struct IoSetup {
IoSetup() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
}IoSetup;
using Int = int;
using ll = long long;
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int SMOD = 1000000007;
constexpr int NMOD = 998244353;
constexpr int dx[]={1,0,-1,0,1,1,-1,-1};
constexpr int dy[]={0,-1,0,1,-1,1,-1,1};
inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T&b){if(a<b)return(a=b,1);return 0;}
template<class T>bool chmin(T &a, const T&b){if(b<a)return(a=b,1);return 0;}
struct LowLink{
int n,pos;
vector<int> ord,low,par,blg,num;
vector<vector<int> > G,C,T;
vector<vector<pair<int, int> > > E;
vector<int> ap;
vector<pair<int, int> > bs,cand;
LowLink(int n):n(n),pos(0),ord(n,-1),low(n),
par(n,-1),blg(n,-1),num(n,1),G(n){}
// ord: DFS順のナンバリング
// low: dfs木の葉方向の辺を0回以上, 後退辺を高々1回通って到達可能なordの最小値
// ある辺(u, v)が橋であるとき、ord[u] < low[v]を満たす
// par: 根付き木の親
// blg[v]: 頂点vが属する成分の番号
// num[v]: 頂点vを根とする部分木のサイズ
// G: 与えられる生のグラフ
// C[id]: 成分idに属する頂点のリスト
// blg と C は相互関係
// T[v]: 成分(v, T[v][i]) を結ぶ辺
// 分解後の木となる
// E: DFS木の辺のリスト E[i][j]の(first, second)は辺だけど　E[i]が何を表すかはわからん
// ap: 関節点のリスト
// bs: 橋のリスト 辺(first, second) は橋である
// cand: もしかしたら適当利用なやつで考慮しなくてもいいかもしれない
// public
void add_edge(int u,int v){
G[u].emplace_back(v);
G[v].emplace_back(u);
}
//
bool is_bridge(int u,int v){
if(ord[u]>ord[v]) swap(u,v);
return ord[u]<low[v];
}
void dfs(int v){
ord[v]=low[v]=pos++;
int dup=0;
for(int u:G[v]){
if(u==par[v]){
if(dup) low[v]=min(low[v],ord[u]); //二重辺がある
dup=1;
continue;
}
if(ord[u]<ord[v]) // vを根とした部分木の子(u, x)同士に辺があるときの辺(v, u) みたいなのを除くとき 根から後退辺を考えないようにしてる(?)
cand.emplace_back(min(u,v),max(u,v));
if(~ord[u]){
low[v]=min(low[v],ord[u]);
continue;
}
par[u]=v;
dfs(u);
num[v]+=num[u];
low[v]=min(low[v],low[u]);
if(is_bridge(u,v)) bs.emplace_back(u,v);
if(low[u]>=ord[v]){
E.emplace_back();
while(1){
auto e=cand.back();
cand.pop_back();
E.back().emplace_back(e);
if(make_pair(min(u,v),max(u,v))==e) break;
}
}
}
}
// ナンバリング
void fill_component(int v){
C[blg[v]].emplace_back(v);
for(int u:G[v]){
if(~blg[u]||is_bridge(u,v)) continue;
blg[u]=blg[v];
fill_component(u);
}
}
// 成分ごとにナンバリング
void add_component(int v,int &k){
if(~blg[v]) return;
blg[v]=k++;
C.emplace_back();
fill_component(v);
}
// public
int build(){
for(int i=0;i<n;i++)
if(ord[i]<0) dfs(i);
vector<int> cnt(n,0);
for(int i=0;i<n;i++){
int p=par[i];
if(p<0) continue;
if(par[p]<0) cnt[p]++; // 親が根の時カウント
else if(ord[p]<=low[i]) ap.emplace_back(p);
}
for(int i=0;i<n;i++)
if(cnt[i]>1) ap.emplace_back(i); //次数が1を超過 -> 関節点
sort(ap.begin(),ap.end());
ap.erase(unique(ap.begin(),ap.end()),ap.end());
int k=0;
for(int i=0;i<n;i++) add_component(i,k);
T.assign(k,vector<int>());
for(auto e:bs){
int u=blg[e.first],v=blg[e.second];
T[u].emplace_back(v);
T[v].emplace_back(u);
}
return k;
}
};
int dist[101010];
int u[101010];
void dfs(int v, vector<vector<int>>&G, vector<int>&nv) {
for(int i = 0; i < G[v].size(); i++) {
if(dist[G[v][i]] == INF) {
dist[G[v][i]] = dist[v] + nv[G[v][i]];
dfs(G[v][i], G, nv);
}
}
}
signed main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> u[i];
}
LowLink low(n);
for(int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
low.add_edge(a-1, b-1);
}
auto cn = low.build();
auto G = low.T;
vector<int> nv(G.size(), 0);
for(int i = 0; i < n; i++) {
nv[low.blg[i]] += u[i];
}
memset(dist, 0x3f, sizeof(dist));
dist[0] = nv[0];
dfs(0, G, nv);
int s = 0;
for(int i = 0; i < n; i++) {
if(dist[s] < dist[i]) {
s = i;
}
}
memset(dist, 0x3f, sizeof(dist));
dist[s] = nv[s];
dfs(s, G, nv);
int ans = 0;
for(int i = 0; i < n; i++) {
chmax(ans, dist[i]);
}
cout << ans << endl;
return 0;
}

ステータス

項目 データ
問題 0012 - ダンジョン３
ユーザー名 社会主義共和国連邦
投稿日時 2020-08-17 11:54:35
言語 C++17
状態 Runtime Error
得点 0
ソースコード長 5966 Byte
最大実行時間 87 ms
最大メモリ使用量 21452 KB

セット

セット 得点 Cases
1 ALL 0 / 12 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 29 ms 860 KB
1
in2 AC 28 ms 856 KB
1
in3 AC 28 ms 1004 KB
1
in4 AC 20 ms 944 KB
1
in5 AC 20 ms 888 KB
1
in6 RE 29 ms 824 KB
1
in7 RE 29 ms 884 KB
1
in8 AC 24 ms 948 KB
1
in9 RE 27 ms 1016 KB
1
in10 RE 52 ms 932 KB
1
in11 RE 32 ms 868 KB
1
in12 RE 25 ms 912 KB
1
in13 RE 28 ms 2220 KB
1
in14 RE 44 ms 3428 KB
1
in15 RE 58 ms 7124 KB
1
in16 RE 66 ms 13100 KB
1
in17 RE 33 ms 940 KB
1
in18 RE 33 ms 1000 KB
1
in19 RE 34 ms 932 KB
1
in20 RE 31 ms 932 KB
1
in21 RE 35 ms 1024 KB
1
in22 RE 29 ms 988 KB
1
in23 RE 34 ms 3352 KB
1
in24 RE 39 ms 3816 KB
1
in25 RE 58 ms 8176 KB
1
in26 RE 87 ms 14648 KB
1
in27 RE 60 ms 21428 KB
1
in28 RE 66 ms 21452 KB
1