Submission #881698

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

island

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,m;
vector<vector<int>> adj;
vector<int> v, ssum,res;

int dfs(int x, int ant){

    int sum = v[x];

    for(auto i: adj[x]){
        if(i == ant) continue;
        sum += dfs(i,x);
    }

    ssum[x] = sum;
    return sum;
}

void dfs2(int x, int ant){

    if(ssum[x] < v[ant]) return;
    res[x] = 1;

    for(auto i: adj[x]){
        if(i == ant) continue;
        dfs2(i,x);
    }
    return;
}

signed main(){

    cin >> n >> m;
    adj.resize(n+2);
    v.resize(n+2);
    res.assign(n+2,0);

    ssum.assign(n+2, 0);

    for(int i=1; i<=n; i++) cin >> v[i];

    for(int i=0; i<m; i++){
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(1,0);
    dfs2(1,0);

    for(int i=1; i<=n; i++) cout << res[i];
    cout << endl;
}

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