oj.uz

Submission #601486

# Submission time Handle Problem Language Result Execution time Memory
601486 2022-07-22T05:41:07 Z 반딧불(#8472) Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
ll arr[200002];
ll sum[200002];
bool ans[200002];
vector<int> link[200002];

void dfs(int x, int p=-1){
    sum[x] = arr[x];
    for(auto y: link[x]){
        if(y==p) continue;
        dfs(y, x);
        sum[x] += sum[y];
    }
}

void dfs2(int x, int p=-1){
    if(x==1) ans[x] = 1;
    else if(arr[p] <= sum[x] && ans[p]) ans[x] = 1;
    for(auto y: link[x]){
        if(y==p) continue;
        dfs2(y, x);
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }

    dfs(1);
    dfs2(1);
    for(int i=1; i<=n; i++) printf("%d", ans[i]);
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
island.cpp:33:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
island.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 227 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 3 ms 5012 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 169 ms 20928 KB Output is correct
4 Correct 165 ms 20764 KB Output is correct
5 Correct 185 ms 14632 KB Output is correct
6 Correct 200 ms 14740 KB Output is correct
7 Correct 173 ms 14768 KB Output is correct
8 Correct 210 ms 15024 KB Output is correct
9 Correct 166 ms 14608 KB Output is correct
10 Correct 106 ms 15264 KB Output is correct
11 Correct 116 ms 15476 KB Output is correct
12 Correct 208 ms 14620 KB Output is correct
13 Correct 161 ms 30120 KB Output is correct
14 Correct 159 ms 30164 KB Output is correct
15 Correct 168 ms 30336 KB Output is correct
16 Correct 127 ms 30240 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 189 ms 30252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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