oj.uz

Submission #881698

# Submission time Handle Problem Language Result Execution time Memory
881698 2023-12-01T18:11:57 Z teesla Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 380 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 219 ms 25364 KB Output is correct
4 Correct 154 ms 24108 KB Output is correct
5 Correct 208 ms 20964 KB Output is correct
6 Correct 237 ms 21584 KB Output is correct
7 Correct 229 ms 21836 KB Output is correct
8 Correct 224 ms 21584 KB Output is correct
9 Correct 191 ms 22864 KB Output is correct
10 Correct 156 ms 21184 KB Output is correct
11 Correct 151 ms 21196 KB Output is correct
12 Correct 161 ms 20320 KB Output is correct
13 Correct 163 ms 28376 KB Output is correct
14 Correct 179 ms 28648 KB Output is correct
15 Correct 213 ms 29928 KB Output is correct
16 Correct 157 ms 28904 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 198 ms 29728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1099 ms 432492 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 380 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -