Submission #1097421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097421		HaciyevAlik	Stranded Far From Home (BOI22_island)	C++14	10 / 100	1051 ms	524288 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define oo 100000000000000000
const int mx = 2e5 + 5;

int s[mx], sub[mx];
vector<int> g[mx];
bool ans[mx];
void dfs(int u, int p) {
    sub[u] = s[u];
    for(int v : g[u]) {
        if(v == p) continue;
        dfs(v,u);
        sub[u] += sub[v];
    }
}
void dfs2(int u,int p) {
    if(!ans[p]) ans[u] = false;
    else ans[u] = (sub[u] >= s[p]);
    for(int v : g[u]) {
        if(v == p) continue;
        dfs2(v,u);
    }
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m; cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    for(int i = 1; i <= m; ++i) {
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ans[0] = 1;
    dfs(1,0);
    dfs2(1,0);
    for(int i = 1; i <= n; ++i) {
        cout << ans[i];
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35