#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, M, inp, inp2;
deque<pair<int, int> > d;
vector<int> adjList[200010];
int added[200010];
int P[200010];
int sz[200010];
int num[200100];
int ans;
int numdel[200010];
bool flick[200010];
vector<int> s[200010];
vector<int> rmd[200010];
int find(int x){
return (P[x] == x ? x : P[x] = find(P[x]));
}
bool same(int x, int y){
return find(x) == find(y);
}
int32_t main(){
cin >> N >> M;
deque<pair<int, int> > c;
for(int a=0; a<N; a++){
cin >> inp;
d.push_back({inp, a+1});
}
c = d;
sort(d.begin(), d.end());
for(int a=0; a<M; a++){
cin >> inp >> inp2;
adjList[inp].push_back(inp2);
adjList[inp2].push_back(inp);
}
//some kind of ufds that stores num of deleted kids, total sum
for(int a=1; a<=N; a++){
P[a] = a;
sz[a] = c[a-1].first;
num[a] = 1;
s[a].push_back(a);
}
//for(auto it: d){
// cout << it.first << ' ' << it.second << '\n';
//}
//cout << "hello its over \n\n";
int las=0;
while(!d.empty()){
int cursz = d[0].first;
while(!d.empty() && d[0].first == cursz){
las = d[0].second;
auto it = d[0];
d.pop_front();
//ins d[0]
added[it.second] = true;
for(auto e: adjList[it.second]){
if(added[e] && !same(e, it.second)){
//cout << it.second << " and " << e << " falls under: case ";
e = find(e);
if(sz[e] < it.first){
//cout << "1\n";
//cout << "thus ans from: " << ans << " to ";
ans -= numdel[e];
ans += num[e];
//add s[e] to rmd[it.second] and s[it.second]
//cout << ans << '\n';
vector<int> t = s[e];
//if((int)s[e].size() > (int)s[it.second].size()) swap(s[e], s[it.second]);
//for(auto itt: s[e]) s[it.second].push_back(itt);
//if((int)t.size() > (int)rmd[it.second].size()) swap(t, rmd[it.second]);
//for(auto itt: t) rmd[it.second].push_back(itt);
P[e] = it.second;
numdel[it.second] += num[e];
num[it.second] += num[e];
sz[it.second] += sz[e];
}
else{
//cout << "2\n";
//can do
numdel[it.first] += numdel[e];
num[it.second] += num[e];
P[e] = it.second;
sz[it.second] += sz[e];
//add rmd to rmd and s to s
//if((int)s[e].size() > (int)s[it.second].size()) swap(s[e], s[it.second]);
//for(auto itt: s[e]) s[it.second].push_back(itt);
//if((int)rmd[e].size() > (int)rmd[it.second].size()) swap(rmd[e], rmd[it.second]);
//for(auto itt: rmd[e]) rmd[it.second].push_back(itt);
}
}
}
}
}
for(auto it: rmd[las]){
flick[it] = true;
}
for(int a=1; a<=N; a++){
if(flick[a]) cout << 0;
else cout << 1;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14508 KB |
Output is correct |
| 2 |
Runtime error |
306 ms |
80504 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Runtime error |
305 ms |
78836 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
