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;
typedef long long ll;
const int maxn = 2e3;
int n, m;
vector<ll> a(maxn+5), sum(maxn+5);
vector<vector<int>> g(maxn+5);
vector<bool> work(maxn+5), vis(maxn+5);
void dfs1(int v, int p){
vis[v] = 1, sum[v] = a[v];
for(int u : g[v]){
if(u == p)
continue;
dfs1(u, v);
sum[v]+= sum[u];
}
if(p != -1)
work[v] = (sum[v] >= a[p]);
}
void dfs2(int v, int p){
if(p != -1)
work[v] = min(work[v], work[p]);
for(int u : g[v]){
if(u == p)
continue;
dfs2(u, v);
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs1(1, -1);
work[1] = 1;
dfs2(1, -1);
for(int i = 1; i <= n; i++)
cout << work[i];
cout << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
// cin >> tt;
while(tt--){
solve();
}
}
# | 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... |