oj.uz

Submission #574130

# Submission time Handle Problem Language Result Execution time Memory
574130 2022-06-08T01:28:40 Z eecs Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 14144 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010;
int n, m, a[maxn], vis[maxn];
vector<int> G[maxn];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (m--) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        set<pair<int, int>> cand;
        long long s = 0;
        cand.emplace(0, i);
        while (!cand.empty() && cand.begin()->first <= s) {
            int j = cand.begin()->second;
            s += a[j], vis[j] = i;
            cand.erase(cand.begin());
            for (int k : G[j]) {
                if (i ^ vis[k]) cand.emplace(a[k], k);
            }
        }
        cout << (cand.empty() ? '1' : '0');
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 261 ms 5092 KB Output is correct
5 Correct 196 ms 5092 KB Output is correct
6 Correct 341 ms 5100 KB Output is correct
7 Correct 257 ms 5196 KB Output is correct
8 Correct 165 ms 5076 KB Output is correct
9 Correct 302 ms 5136 KB Output is correct
10 Correct 101 ms 5092 KB Output is correct
11 Correct 113 ms 5088 KB Output is correct
12 Correct 125 ms 5092 KB Output is correct
13 Correct 189 ms 5096 KB Output is correct
14 Correct 111 ms 5096 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Execution timed out 1075 ms 12872 KB Time limit exceeded
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 1083 ms 13128 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 261 ms 5092 KB Output is correct
5 Correct 196 ms 5092 KB Output is correct
6 Correct 341 ms 5100 KB Output is correct
7 Correct 257 ms 5196 KB Output is correct
8 Correct 165 ms 5076 KB Output is correct
9 Correct 302 ms 5136 KB Output is correct
10 Correct 101 ms 5092 KB Output is correct
11 Correct 113 ms 5088 KB Output is correct
12 Correct 125 ms 5092 KB Output is correct
13 Correct 189 ms 5096 KB Output is correct
14 Correct 111 ms 5096 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Execution timed out 1086 ms 14144 KB Time limit exceeded
18 Halted 0 ms 0 KB -