#include <bits/stdc++.h>
//#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
#define debug2(x, y) cout << #x << ": " << x << ' ' << #y << ": " << y << '\n'
#define debug3(x, y, z) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << '\n'
#define debug4(x, y, z, w) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << ' ' << #w << ": " << w << '\n'
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int inf = 1000000000000000000, mod = 998244353;
int n, m, root[200005], val[200005], sz[200005];
pi s[200005];
vector <int> nodes[200005];
vector <int> adj[200005];
bool processed[200005], ans[200005];
int getroot(int x){
if(x == root[x]) return x;
else return root[x] = getroot(root[x]);
}
void merge(int x, int y){
int rootx = getroot(x), rooty = getroot(y);
//debug4(x, rootx, y, rooty);
if(rootx == rooty) return;
if(sz[rootx] < sz[rooty]) swap(rootx, rooty), swap(nodes[rootx], nodes[rooty]);
root[rooty] = rootx, sz[rootx] += sz[rooty], val[rootx] += val[rooty];
for(auto it = nodes[rooty].begin(); it != nodes[rooty].end(); it++) nodes[rootx].pb(*it);
nodes[rooty].clear();
//cout << "merged: " << x << ", " << y << '\n';
}
void mark(int x){
for(auto it = nodes[x].begin(); it != nodes[x].end(); it++) ans[*it] = 0;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
fill(ans+1, ans+n+1, 0);
for(int i = 1; i <= n; i++){
cin >> s[i].fi;
s[i].se = i, root[i] = i, val[i] = s[i].fi, sz[i] = 1;
nodes[i].pb(i);
}
for(int i = 1; i <= m; i++){
int a, b; cin >> a >> b;
adj[a].pb(b), adj[b].pb(a);
}
sort(s+1, s+n+1);
for(int i = 1; i <= n; i++){
processed[s[i].se] = 1;
for(int j : adj[s[i].se]){
//debug3(s[i].se, j, processed[j]);
if(!processed[j]) continue;
int k = getroot(j);
//debug4(s[i].se, s[i].fi, k, val[k]);
if(s[i].fi > val[k]){
nodes[k].clear();
}
merge(s[i].se, k);
}
}
for(int i = 1; i <= n; i++){
if(i != getroot(i)) continue;
for(auto it = nodes[i].begin(); it != nodes[i].end(); it++) ans[*it] = 1;
}
for(int i = 1; i <= n; i++) cout << ans[i];
}
Compilation message
island.cpp:16:17: warning: overflow in conversion from 'long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
16 | const int inf = 1000000000000000000, mod = 998244353;
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
9812 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Incorrect |
172 ms |
29204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
211 ms |
26844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 2 |
Incorrect |
218 ms |
26816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
9812 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
