//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int N = 2e5 + 7;
const int inf = 1e9 + 7;
int n,m,s[N],marked[N],ans[N],tar[N],sum[N],bruh[N];
vector < int > graph[N],adj[N];
struct Component{
set < pair < int , int > > edges;// outgoing edges of the component
int parent , representative , value;
} dsu[N];
int find(int a){
if(dsu[a].parent == dsu[a].representative)return dsu[a].representative;
else return dsu[a].parent = find(dsu[a].parent);
}
void merge(int a , int b){
a = find(a) , b = find(b);
if(a == b)return;
if(sz(dsu[a].edges) > sz(dsu[b].edges))dsu[a].edges.swap(dsu[b].edges);
dsu[a].parent = dsu[b].representative;
dsu[b].value += dsu[a].value;
vector < pair < int , int > > will_delete;
// cout << "merge : " << a << " , " << b << endl;
// cout << "edges of a : ";for(auto itr : dsu[a].edges)cout << itr.first << "," << itr.second << " ";cout << endl;
// cout << "edges of b : ";for(auto itr : dsu[b].edges)cout << itr.first << "," << itr.second << " ";cout << endl;
for(auto itr : dsu[a].edges){
if(dsu[b].edges.count({itr.second , itr.first}) == 0){
dsu[b].edges.insert(itr);
}
else{
will_delete.push_back({itr.second , itr.first});
}
}
for(auto itr : will_delete){
dsu[b].edges.extract(itr);
}
dsu[a].edges.clear();
// cout << "final of b : ";for(auto itr : dsu[b].edges)cout << itr.first << "," << itr.second << " ";cout << endl;
}
void solve(){
cin >> n >> m;
pair < int , int > village[n];
vector < int > compr;
for(int i = 1;i<=n;i++){
cin >> s[i];
compr.push_back(s[i]);
village[i-1] = {s[i] , i};
dsu[i].representative = dsu[i].parent = i;
dsu[i].value = s[i];
tar[i] = inf;
}
sort(all(compr));
compr.resize(unique(all(compr)) - compr.begin());
sort(village , village + n);
for(int i = 0;i<m;i++){
int ai,bi;
cin >> ai >> bi;
dsu[ai].edges.insert({ai , bi});
dsu[bi].edges.insert({bi , ai});
graph[ai].push_back(bi);
graph[bi].push_back(ai);
}
int lp0 = 0 , lp1 = 0;
for(auto si : compr){
while(lp1 < n and village[lp1].first <= si){
marked[village[lp1].second] = 1;
lp1++;
}
while(lp0 < n and village[lp0].first <= si){
for(auto itr : graph[village[lp0].second]){
if(marked[itr] == 1){
merge(itr , village[lp0].second);
}
}
for(auto itr : dsu[find(village[lp0].second)].edges){
adj[itr.second].push_back(village[lp0].second);
}
bruh[village[lp0].second] = find(village[lp0].second);
sum[village[lp0].second] = dsu[village[lp0].second].value;
lp0++;
}
}
for(int i = 1;i<=n;i++){
sort(all(adj[village[i].second]));
adj[village[i].second].resize(unique(all(adj[village[i].second])) - adj[village[i].second].begin());
}
// cout << "dsu : " << endl;
// for(int i = 1;i<=n;i++){
// cout << " " << i << endl;
// for(auto itr : adj[i])cout << " " << itr << " ";cout << endl;
// }
// cout << "###########################################################################" << endl;
memset(ans , -1 , sizeof(ans));
tar[village[n-1].second] = 0;
for(int i = n-1;i>=0;i--){
// cout << village[i].second << " : " << bruh[village[i].second] << endl;
if(bruh[village[i].second] == village[i].second){
if(tar[village[i].second] <= sum[village[i].second]){
ans[village[i].second] = 1;
for(auto itr : adj[village[i].second]){
tar[itr] = min(tar[itr] , s[village[i].second]);
}
}
else ans[village[i].second] = 0;
}
}
for(int i = 1;i<=n;i++){
cout << ans[bruh[i]];
}
cout << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
25432 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25436 KB |
Output is correct |
| 3 |
Correct |
5 ms |
25436 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
26716 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25436 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25436 KB |
Output is correct |
| 3 |
Incorrect |
245 ms |
59188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25432 KB |
Output is correct |
| 2 |
Incorrect |
427 ms |
60468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25432 KB |
Output is correct |
| 2 |
Execution timed out |
1046 ms |
142296 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
25432 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25436 KB |
Output is correct |
| 3 |
Correct |
5 ms |
25436 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
26716 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
