#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct info{
int node;
ll people;
bool operator <(const info &i) const{
return people > i.people;
}
};
int N, M;
vector<ll> A;
vector<pair<ll, int>> A1;
vector<bool> taken, vis;
vector<vector<int>> graph;
vector<ll> P;
vector<ll> S;
vector<ll> R;
vector<set<int>> sets;
vector<int> parent;
void dfs(int curr){
vis[curr] = true;
vector<int> adj = graph[curr];
P[curr] = A[curr];
for(int a : adj){
if(vis[a]) continue;
dfs(a);
P[curr] += P[a];
}
}
void solver(int curr, int p, vector<int> &ans){
vis[curr] = true;
vector<int> adj = graph[curr];
if((int)adj.size() == 1 && curr){
if(P[curr] >= A[p]){
ans[curr] = 1;
}else{
ans[curr] = 0;
}
return;
}
for(int a : adj){
if(vis[a]) continue;
if(curr){
if(P[curr] >= A[p]){
ans[curr] = 1;
}else{
ans[curr] = 0;
continue;
}
}
solver(a, curr, ans);
}
}
int getParent(int a){
if(parent[a] == a) return a;
return parent[a] = getParent(parent[a]);
}
void unionFind(int a, int b){
int x = getParent(a);
int y = getParent(b);
if(x == y) return;
if(R[x] < R[y]) swap(x, y);
parent[y] = x;
S[x] += S[y];
R[x] += R[y];
for(int c : sets[y])
sets[x].insert(c);
// rank[y] = rank[x];
}
int dfs1(int curr, vector<int> &ans){
vis[curr] = true;
if(ans[curr] == 0) return 0;
vector<int> adj = graph[curr];
for(int a : adj){
if(vis[a] || A[a] < A[curr]) continue;
int ret = dfs1(a, ans);
if(ret == 0)
ans[curr] = 0;
}
return 1;
}
void solve(){
cin>>N>>M;
A.assign(N, 0);
A1.assign(N, pair<ll, int>());
P.assign(N, 0);
graph.assign(N, vector<int>());
vis.assign(N, false);
parent.assign(N, false);
R.assign(N, 1);
S.assign(N, 0);
sets.assign(N, set<int>());
for(int i = 0; i < N; i++){
int v;
cin>>v;
A[i] = v;
A1[i] = {v, i};
S[i] = v;
parent[i] = i;
sets[i].insert(i);
}
for(int i = 0; i < M; i++){
int a, b;
cin>>a>>b;
a--;
b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
sort(A1.begin(), A1.end());
vector<int> ans(N, 1);
for(int i = 0; i < N; i++){
int color = A1[i].second;
ll abitants = A1[i].first;
vector<int> adj = graph[color];
int mn = INT_MAX;
for(int a : adj){
if(A[a] > abitants){
if(A[a] < mn) mn = A[a];
continue;
}
unionFind(color, a);
// cout<<color<<" "<<a<<endl;
}
int p = getParent(color);
// cout<<"DEBUG-->"<<color<<" "<<S[p]<<endl;
if(i < N-1 && S[p] < mn && mn != INT_MAX){
ans[color] = 0;
for(int x : sets[p]) ans[x] = 0;
// non solo color, ma l'intero componente
}
}
for(int a : ans) cout<<a;
cout<<endl;
/*
bool subtask3 = true;
for(int i = 0; i < M; i++){
int a, b;
cin>>a>>b;
a--;
b--;
graph[a].push_back(b);
graph[b].push_back(a);
subtask3 &= abs(a-b) == 1;
}
vector<int> ans(N, 2);
ll sum = accumulate(A.begin(), A.end(), 0LL);
bool subtask1 = (N <= 2000 && M <= 2000);
if(subtask1){
int last_color = N;
for(int color = 0; color < last_color; color++){
if(ans[color] != 2) continue;
priority_queue<info> pq;
// inizializzo la pq
vector<int> adj = graph[color];
taken.assign(N, false);
taken[color] = true;
for(int a : adj)
pq.push({a, A[a]});
ll total = A[color];
stack<int> nodes;
while(!pq.empty()){
info i = pq.top();
pq.pop();
int node = i.node;
ll abitants = i.people;
if(taken[node]) continue;
taken[node] = true;
if(abitants > total)
break;
if(ans[node] == 1){
total = sum;
break;
}
nodes.push(node);
total += abitants;
vector<int> adj = graph[node];
for(int a : adj){
if(taken[a]) continue;
pq.push({a, A[a]});
}
}
// se ans[color] è false, allora saranno false anche tutti quelli
// che sono stati convinti durante il processo e quindi è inutile
// ricalcolarli
ans[color] = total == sum;
if(!ans[color]){
while(!nodes.empty()){
ans[nodes.top()] = 0;
nodes.pop();
}
}
}
for(int i = 0; i < N; i++) cout<<ans[i];
cout<<endl;
return;
}
if(subtask3){
vector<ll> pref_sum(N+1, 0);
for(int i = 0; i < N; i++){
pref_sum[i+1] += pref_sum[i] + A[i];
}
set<int> s;
ans[A1[0].second] = 1;
s.insert(A1[0].second);
for(int i = 1; i < N; i++){
int color = A1[i].second;
// mi serve il primo abitante sulla sinistra già preso e
// il primo abitante sulla destra già preso cioè ans[i] = true;
auto r = s.lower_bound(color);
auto l = r;
int r_idx = 0;
int l_idx = 0;
if(l == s.begin()){
l_idx = -1;
}else l_idx = *(--l);
if(r == s.end()){
r_idx = N;
}else r_idx = *r;
// cout<<"DEBUG-->"<<color<<" "<<l_idx<<" "<<r_idx<<endl;
if(l_idx == -1)
ans[color] = (pref_sum[r_idx] - pref_sum[l_idx+1]) >= A[r_idx];
else if(r_idx == N)
ans[color] = (pref_sum[r_idx] - pref_sum[l_idx+1]) >= A[l_idx];
else ans[color] = (pref_sum[r_idx] - pref_sum[l_idx+1]) >= min(A[r_idx], A[l_idx]);
if(ans[color])
s.insert(color);
}
for(int i = 0; i < N; i++) cout<<ans[i];
cout<<endl;
return;
}
dfs(0);
vis.assign(N, false);
ans.assign(N, false);
ans[0] = 1;
solver(0, -1, ans);
for(int i = 0; i < N; i++) cout<<ans[i];
cout<<endl;
*/
}
int main(){
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
700 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
341 ms |
55656 KB |
Output is correct |
| 4 |
Incorrect |
316 ms |
53260 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
612 ms |
97596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
619 ms |
69316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
700 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
