This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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<bool> taken;
vector<vector<int>> graph;
void solve(){
cin>>N>>M;
A.assign(N, 0);
graph.assign(N, vector<int>());
for(ll &v:A) cin>>v;
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);
}
vector<bool> ans(N, 1);
ll sum = accumulate(A.begin(), A.end(), 0LL);
for(int color = 0; color < N; color++){
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];
int cnt = 1;
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;
total += abitants;
vector<int> adj = graph[node];
for(int a : adj){
if(taken[a]) continue;
pq.push({a, A[a]});
}
}
ans[color] = total == sum;
}
for(int i = 0; i < N; i++) cout<<ans[i];
cout<<endl;
}
int main(){
solve();
return 0;
}
Compilation message (stderr)
island.cpp: In function 'void solve()':
island.cpp:55:7: warning: unused variable 'cnt' [-Wunused-variable]
55 | int cnt = 1;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |