oj.uz

Submission #1097421

# Submission time Handle Problem Language Result Execution time Memory
1097421 2024-10-07T09:40:54 Z HaciyevAlik 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
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 296 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 1 ms 6492 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 80 ms 25260 KB Output is correct
4 Correct 67 ms 23892 KB Output is correct
5 Correct 72 ms 19796 KB Output is correct
6 Correct 82 ms 20308 KB Output is correct
7 Correct 78 ms 20308 KB Output is correct
8 Correct 79 ms 20364 KB Output is correct
9 Correct 68 ms 21332 KB Output is correct
10 Correct 52 ms 19904 KB Output is correct
11 Correct 54 ms 19908 KB Output is correct
12 Correct 72 ms 19028 KB Output is correct
13 Correct 72 ms 30196 KB Output is correct
14 Correct 74 ms 30504 KB Output is correct
15 Correct 83 ms 31828 KB Output is correct
16 Correct 61 ms 30800 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 86 ms 31668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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