oj.uz

Submission #1024911

# Submission time Handle Problem Language Result Execution time Memory
1024911 2024-07-16T12:16:44 Z overwatch9 Stranded Far From Home (BOI22_island) C++17
10 / 100
 756 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 1;
ll S[maxn];
vector <int> adj[maxn];
bool ans[maxn];
ll sz[maxn];
void dfs(int s, int p) {
    sz[s] = S[s];
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        dfs(i, s);
        sz[s] += sz[i];
    }
}
vector <int> v;
void dfs2(int s, int p) {
    if (sz[s] >= S[p] && ans[p] == true)
        ans[s] = true;
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        dfs2(i, s);
    }
}
int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> S[i];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int root = max_element(S, S + n + 1) - S;
    dfs(root, root);
    ans[root] = root;
    for (auto i : adj[root]) {
        dfs2(i, root);
      	v.clear();
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i];
    cout << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 253 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 1 ms 6492 KB Output is correct
3 Correct 152 ms 21076 KB Output is correct
4 Correct 130 ms 21076 KB Output is correct
5 Correct 144 ms 14580 KB Output is correct
6 Correct 147 ms 14928 KB Output is correct
7 Correct 148 ms 14892 KB Output is correct
8 Correct 167 ms 14932 KB Output is correct
9 Correct 173 ms 14672 KB Output is correct
10 Correct 114 ms 15556 KB Output is correct
11 Correct 110 ms 15556 KB Output is correct
12 Correct 125 ms 14928 KB Output is correct
13 Correct 126 ms 30544 KB Output is correct
14 Correct 125 ms 30292 KB Output is correct
15 Correct 154 ms 30544 KB Output is correct
16 Correct 130 ms 30096 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Incorrect 152 ms 23380 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 Runtime error 756 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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