oj.uz

Submission #850411

# Submission time Handle Problem Language Result Execution time Memory
850411 2023-09-16T14:10:21 Z MinaRagy06 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 13132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

const int N = 200'005;
bool in[N], bad[N];
vector<int> adj[N];
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int st = 0; st < n; st++) {
        if (bad[st]) {
            cout << 0;
            continue;
        }
        for (int i = 0; i < n; i++) {
            in[i] = 0;
        }
        in[st] = 1;
        priority_queue<pair<int, int>> pq;
        for (auto nxt : adj[st]) {
            pq.push({-a[nxt], nxt});
        }
        ll ttl = a[st];
        while (pq.size()) {
            int cost = -pq.top().first;
            int node = pq.top().second;
            pq.pop();
            if (in[node]) continue;
            if (ttl < cost) {
                break;
            }
            ttl += cost;
            in[node] = 1;
            for (auto nxt : adj[node]) {
                if (!in[nxt]) {
                    pq.push({-a[nxt], nxt});
                }
            }
        }
        int ok = 1;
        for (int i = 0; i < n; i++) {
            ok &= in[i];
        }
        if (!ok) {
            for (int i = 0; i < n; i++) {
                if (in[i]) {
                    bad[i] = 1;
                }
            }
        }
        cout << ok;
    }
    cout << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 4964 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 185 ms 5212 KB Output is correct
5 Correct 136 ms 5212 KB Output is correct
6 Correct 274 ms 5212 KB Output is correct
7 Correct 179 ms 5212 KB Output is correct
8 Correct 143 ms 5464 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 47 ms 5212 KB Output is correct
11 Correct 45 ms 5212 KB Output is correct
12 Correct 49 ms 5208 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 14 ms 5208 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 4964 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 185 ms 5212 KB Output is correct
5 Correct 136 ms 5212 KB Output is correct
6 Correct 274 ms 5212 KB Output is correct
7 Correct 179 ms 5212 KB Output is correct
8 Correct 143 ms 5464 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 47 ms 5212 KB Output is correct
11 Correct 45 ms 5212 KB Output is correct
12 Correct 49 ms 5208 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 14 ms 5208 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 1 ms 4956 KB Output is correct
17 Execution timed out 1060 ms 13132 KB Time limit exceeded
18 Halted 0 ms 0 KB -