#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define ll long long
using namespace std;
vector<int> dsu,sz,ans;
vector<ll> sum;
vector<set<int> > nodes;
void build(int n){
dsu.resize(n+1);
sz.resize(n+1);
for(int i=1;i<=n;i++) dsu[i]=i,sz[i]=1,nodes[i].insert(i);
}
int query(int x){
if(dsu[x]==x) return x;
return query(dsu[x]);
}
void unite(int a,int b,int ori){
a=query(a),b=query(b);
if(a==b) return;
if(ori>sum[b]){
for(auto x:nodes[b]){
ans[x]=0;
}
nodes[b].clear();
}
if(sz[a]<sz[b]) swap(a,b);
dsu[b]=a;
sz[a]+=sz[b];
sum[a]+=sum[b];
for(auto x:nodes[b]) if(ans[x]==-1) nodes[a].insert(x);
nodes[b].clear();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
vector<vector<int> > graph;
ans.resize(n+1,-1);
nodes.resize(n+1);
graph.resize(n+1);
sum.resize(n+1);
vector<pair<ll,int> > val(n);
for(int i=1;i<=n;i++) cin>>val[i-1].first,val[i-1].second=i,sum[i]=val[i-1].first;
int a,b;
for(int i=0;i<m;i++){
cin>>a>>b;
if(val[a-1]<val[b-1]) graph[b].push_back(a);
else graph[a].push_back(b);
}
sort(val.begin(),val.end());
build(n);
for(int i=0;i<n;){
int now=i;
while(now<n&&val[i].first==val[now].first){
for(auto x:graph[val[now].second]){
unite(val[now].second,x,val[now].first);
}
now++;
}
if(now==n) break;
for(int j=i;j<now;j++){
int mum=query(val[j].second);
//cout<<val[j].second<<" "<<sum[mum]<<"\n";
if(sum[mum]<val[now].first){
for(auto x:nodes[mum]){
ans[x]=0;
}
nodes[mum].clear();
}
}
i=now;
}
for(int i=1;i<=n;i++){
if(ans[i]==-1) cout<<1;
else cout<<0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
584 KB |
Output is correct |
7 |
Correct |
2 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
480 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
2 ms |
592 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
142 ms |
35972 KB |
Output is correct |
4 |
Correct |
138 ms |
39164 KB |
Output is correct |
5 |
Correct |
172 ms |
35776 KB |
Output is correct |
6 |
Correct |
191 ms |
39212 KB |
Output is correct |
7 |
Correct |
189 ms |
39336 KB |
Output is correct |
8 |
Correct |
142 ms |
41696 KB |
Output is correct |
9 |
Correct |
133 ms |
38464 KB |
Output is correct |
10 |
Correct |
75 ms |
35376 KB |
Output is correct |
11 |
Correct |
137 ms |
40656 KB |
Output is correct |
12 |
Correct |
165 ms |
39716 KB |
Output is correct |
13 |
Correct |
126 ms |
40168 KB |
Output is correct |
14 |
Correct |
127 ms |
40364 KB |
Output is correct |
15 |
Correct |
128 ms |
41676 KB |
Output is correct |
16 |
Correct |
117 ms |
40604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
277 ms |
36280 KB |
Output is correct |
3 |
Correct |
261 ms |
39728 KB |
Output is correct |
4 |
Correct |
151 ms |
41728 KB |
Output is correct |
5 |
Correct |
133 ms |
40124 KB |
Output is correct |
6 |
Correct |
281 ms |
39728 KB |
Output is correct |
7 |
Correct |
164 ms |
41724 KB |
Output is correct |
8 |
Correct |
169 ms |
41776 KB |
Output is correct |
9 |
Correct |
100 ms |
40628 KB |
Output is correct |
10 |
Correct |
115 ms |
37948 KB |
Output is correct |
11 |
Correct |
147 ms |
38228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
253 ms |
36048 KB |
Output is correct |
3 |
Correct |
250 ms |
39212 KB |
Output is correct |
4 |
Correct |
303 ms |
39408 KB |
Output is correct |
5 |
Correct |
312 ms |
40048 KB |
Output is correct |
6 |
Correct |
274 ms |
37756 KB |
Output is correct |
7 |
Correct |
157 ms |
39196 KB |
Output is correct |
8 |
Correct |
99 ms |
40512 KB |
Output is correct |
9 |
Correct |
98 ms |
20992 KB |
Output is correct |
10 |
Correct |
297 ms |
39684 KB |
Output is correct |
11 |
Correct |
162 ms |
38212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
584 KB |
Output is correct |
7 |
Correct |
2 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
480 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
2 ms |
592 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
142 ms |
35972 KB |
Output is correct |
18 |
Correct |
138 ms |
39164 KB |
Output is correct |
19 |
Correct |
172 ms |
35776 KB |
Output is correct |
20 |
Correct |
191 ms |
39212 KB |
Output is correct |
21 |
Correct |
189 ms |
39336 KB |
Output is correct |
22 |
Correct |
142 ms |
41696 KB |
Output is correct |
23 |
Correct |
133 ms |
38464 KB |
Output is correct |
24 |
Correct |
75 ms |
35376 KB |
Output is correct |
25 |
Correct |
137 ms |
40656 KB |
Output is correct |
26 |
Correct |
165 ms |
39716 KB |
Output is correct |
27 |
Correct |
126 ms |
40168 KB |
Output is correct |
28 |
Correct |
127 ms |
40364 KB |
Output is correct |
29 |
Correct |
128 ms |
41676 KB |
Output is correct |
30 |
Correct |
117 ms |
40604 KB |
Output is correct |
31 |
Correct |
1 ms |
320 KB |
Output is correct |
32 |
Correct |
277 ms |
36280 KB |
Output is correct |
33 |
Correct |
261 ms |
39728 KB |
Output is correct |
34 |
Correct |
151 ms |
41728 KB |
Output is correct |
35 |
Correct |
133 ms |
40124 KB |
Output is correct |
36 |
Correct |
281 ms |
39728 KB |
Output is correct |
37 |
Correct |
164 ms |
41724 KB |
Output is correct |
38 |
Correct |
169 ms |
41776 KB |
Output is correct |
39 |
Correct |
100 ms |
40628 KB |
Output is correct |
40 |
Correct |
115 ms |
37948 KB |
Output is correct |
41 |
Correct |
147 ms |
38228 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
253 ms |
36048 KB |
Output is correct |
44 |
Correct |
250 ms |
39212 KB |
Output is correct |
45 |
Correct |
303 ms |
39408 KB |
Output is correct |
46 |
Correct |
312 ms |
40048 KB |
Output is correct |
47 |
Correct |
274 ms |
37756 KB |
Output is correct |
48 |
Correct |
157 ms |
39196 KB |
Output is correct |
49 |
Correct |
99 ms |
40512 KB |
Output is correct |
50 |
Correct |
98 ms |
20992 KB |
Output is correct |
51 |
Correct |
297 ms |
39684 KB |
Output is correct |
52 |
Correct |
162 ms |
38212 KB |
Output is correct |
53 |
Correct |
0 ms |
212 KB |
Output is correct |
54 |
Correct |
1 ms |
316 KB |
Output is correct |
55 |
Correct |
0 ms |
212 KB |
Output is correct |
56 |
Correct |
1 ms |
596 KB |
Output is correct |
57 |
Correct |
2 ms |
596 KB |
Output is correct |
58 |
Correct |
1 ms |
596 KB |
Output is correct |
59 |
Correct |
1 ms |
588 KB |
Output is correct |
60 |
Correct |
1 ms |
468 KB |
Output is correct |
61 |
Correct |
1 ms |
724 KB |
Output is correct |
62 |
Correct |
2 ms |
680 KB |
Output is correct |
63 |
Correct |
1 ms |
588 KB |
Output is correct |
64 |
Correct |
2 ms |
596 KB |
Output is correct |
65 |
Correct |
1 ms |
596 KB |
Output is correct |
66 |
Correct |
1 ms |
596 KB |
Output is correct |
67 |
Correct |
146 ms |
39812 KB |
Output is correct |
68 |
Correct |
155 ms |
40340 KB |
Output is correct |
69 |
Correct |
216 ms |
38092 KB |
Output is correct |
70 |
Correct |
289 ms |
39220 KB |
Output is correct |
71 |
Correct |
273 ms |
39380 KB |
Output is correct |
72 |
Correct |
182 ms |
41612 KB |
Output is correct |
73 |
Correct |
155 ms |
38492 KB |
Output is correct |
74 |
Correct |
112 ms |
35392 KB |
Output is correct |
75 |
Correct |
187 ms |
40672 KB |
Output is correct |
76 |
Correct |
172 ms |
39696 KB |
Output is correct |
77 |
Correct |
168 ms |
40176 KB |
Output is correct |
78 |
Correct |
142 ms |
40332 KB |
Output is correct |
79 |
Correct |
135 ms |
41656 KB |
Output is correct |
80 |
Correct |
108 ms |
40548 KB |
Output is correct |
81 |
Correct |
321 ms |
39328 KB |
Output is correct |
82 |
Correct |
299 ms |
39580 KB |
Output is correct |
83 |
Correct |
176 ms |
41728 KB |
Output is correct |
84 |
Correct |
147 ms |
40116 KB |
Output is correct |
85 |
Correct |
303 ms |
39620 KB |
Output is correct |
86 |
Correct |
154 ms |
41676 KB |
Output is correct |
87 |
Correct |
154 ms |
41768 KB |
Output is correct |
88 |
Correct |
138 ms |
37936 KB |
Output is correct |
89 |
Correct |
178 ms |
38216 KB |
Output is correct |
90 |
Correct |
304 ms |
39184 KB |
Output is correct |
91 |
Correct |
323 ms |
39168 KB |
Output is correct |
92 |
Correct |
359 ms |
39420 KB |
Output is correct |
93 |
Correct |
310 ms |
40032 KB |
Output is correct |
94 |
Correct |
236 ms |
37788 KB |
Output is correct |
95 |
Correct |
158 ms |
39192 KB |
Output is correct |
96 |
Correct |
102 ms |
40536 KB |
Output is correct |
97 |
Correct |
98 ms |
21016 KB |
Output is correct |
98 |
Correct |
298 ms |
39588 KB |
Output is correct |
99 |
Correct |
203 ms |
38216 KB |
Output is correct |
100 |
Correct |
28 ms |
4020 KB |
Output is correct |
101 |
Correct |
298 ms |
39380 KB |
Output is correct |
102 |
Correct |
166 ms |
31656 KB |
Output is correct |
103 |
Correct |
179 ms |
33512 KB |
Output is correct |
104 |
Correct |
266 ms |
38652 KB |
Output is correct |