oj.uz

Submission #714791

# Submission time Handle Problem Language Result Execution time Memory
714791 2023-03-25T09:21:31 Z Toxtaq Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>g;
vector<int>num;
vector<long long>cnt;
vector<int>canTraverse; /// 0-unchecked, 1-false, 2-true
void calc(int u, int par){
    cnt[u] = num[u];
    for(int v : g[u]){
        if(v != par){
            calc(v, u);
            cnt[u] += cnt[v];
        }
    }
}
void dfs(int u, int par){
    if(canTraverse[par] == 1)canTraverse[u] = 1;
    else{
        canTraverse[u] = (cnt[u] >= num[par]) + 1;
    }
    for(int v : g[u]){
        if(v != par){
            dfs(v, u);
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    g.resize(n + 1);
    num.resize(n + 1);
    cnt.resize(n + 1);
    canTraverse.resize(n + 1);
    for(int i = 1;i <= n;++i)cin >> num[i];
    for(int i = 0;i < m;++i){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    calc(1, 1);
    dfs(1, 1);
    for(int i = 1;i <= n;++i){
        if(canTraverse[i] == 2)cout << 1;
        else cout << 0;
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 283 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 301 ms 19516 KB Output is correct
4 Correct 257 ms 19524 KB Output is correct
5 Correct 297 ms 14212 KB Output is correct
6 Correct 316 ms 14572 KB Output is correct
7 Correct 316 ms 14652 KB Output is correct
8 Correct 315 ms 14640 KB Output is correct
9 Correct 286 ms 14484 KB Output is correct
10 Correct 208 ms 15284 KB Output is correct
11 Correct 210 ms 15316 KB Output is correct
12 Correct 299 ms 14692 KB Output is correct
13 Correct 292 ms 27028 KB Output is correct
14 Correct 251 ms 27072 KB Output is correct
15 Correct 326 ms 27084 KB Output is correct
16 Correct 203 ms 26804 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 322 ms 26844 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 212 KB Output is correct
2 Execution timed out 1084 ms 269816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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