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);
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];
while(!pq.empty()){
info i = pq.top();
pq.pop();
int node = i.node;
taken[node] = true;
ll abitants = i.people;
if(abitants > total){
ans[color] = 0;
break;
}
total += abitants;
vector<int> adj = graph[node];
for(int a : adj){
if(taken[a]) continue;
pq.push({a, A[a]});
}
}
}
for(int i = 0; i < N; i++) cout<<ans[i]<<" ";
cout<<endl;
}
int main(){
solve();
return 0;
}
# | 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... |