oj.uz

Submission #850470

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

const int N = 200'005;
int par[N], sz[N], bad[N], a[N];
ll cnt[N];
set<array<int, 3>> adj[N];
pair<int, int> find(int u) {
    if (par[u] == u) {
        return {u, bad[u]};
    }
    pair<int, int> v = find(par[u]);
    bad[u] |= v.second;
    par[u] = v.first;
    return {par[u], bad[u]};
}
void join(int u, int v) {
    u = find(u).first, v = find(v).first;
    if (u == v) return;
    par[v] = u, sz[u] += sz[v], cnt[u] += cnt[v];
    for (auto [vnxt, nxt, src] : adj[v]) {
        int x = find(nxt).first;
        if (x != u) {
            adj[u].insert({a[nxt], nxt, src});
        } else {
            adj[u].erase({a[src], src, nxt});
        }
    }
    adj[v].clear();
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        par[i] = i, sz[i] = 1, bad[i] = 0;
        cin >> cnt[i];
        a[i] = cnt[i];
    }
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        u--, v--;
        adj[u].insert({a[v], v, u});
        adj[v].insert({a[u], u, v});
    }
    priority_queue<pair<ll, int>> pq;
    for (int i = 0; i < n; i++) {
        pq.push({-cnt[i], i});
    }
    while (pq.size()) {
        int node = pq.top().second;
        ll val = -pq.top().first;
        pq.pop();
        if (node != par[node]) {
            continue;
        }
        if (val != cnt[node]) {
            continue;
        }
        if (sz[node] == n) {
            continue;
        }
        int x = -1;
        for (auto [vnxt, nxt, src] : adj[node]) {
            if (val >= vnxt) {
                x = find(nxt).first;
                break;
            }
        }
        if (x == -1) {
            bad[node] = 1;
            continue;
        }
        join(node, x);
        int New = find(node).first;
        pq.push({-cnt[New], New});
    }
    for (int i = 0; i < n; i++) {
        cout << !find(i).second;
    }
    cout << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 5 ms 13144 KB Output is correct
5 Correct 5 ms 13144 KB Output is correct
6 Correct 5 ms 13144 KB Output is correct
7 Correct 5 ms 13144 KB Output is correct
8 Correct 5 ms 13144 KB Output is correct
9 Correct 53 ms 13264 KB Output is correct
10 Correct 4 ms 13144 KB Output is correct
11 Correct 4 ms 13148 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 4 ms 13144 KB Output is correct
14 Correct 5 ms 13144 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 297 ms 45280 KB Output is correct
4 Correct 268 ms 43968 KB Output is correct
5 Correct 299 ms 43460 KB Output is correct
6 Correct 299 ms 43716 KB Output is correct
7 Correct 301 ms 44224 KB Output is correct
8 Correct 358 ms 44224 KB Output is correct
9 Correct 296 ms 44480 KB Output is correct
10 Correct 387 ms 55716 KB Output is correct
11 Execution timed out 1032 ms 55748 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 351 ms 45528 KB Output is correct
3 Correct 334 ms 43716 KB Output is correct
4 Correct 242 ms 44992 KB Output is correct
5 Correct 229 ms 44224 KB Output is correct
6 Correct 332 ms 44992 KB Output is correct
7 Correct 198 ms 44480 KB Output is correct
8 Correct 199 ms 45508 KB Output is correct
9 Correct 109 ms 43764 KB Output is correct
10 Correct 251 ms 43712 KB Output is correct
11 Correct 292 ms 45432 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 433 ms 45208 KB Output is correct
3 Correct 407 ms 45504 KB Output is correct
4 Correct 412 ms 44556 KB Output is correct
5 Correct 331 ms 44140 KB Output is correct
6 Correct 372 ms 44224 KB Output is correct
7 Execution timed out 1038 ms 55416 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 5 ms 13144 KB Output is correct
5 Correct 5 ms 13144 KB Output is correct
6 Correct 5 ms 13144 KB Output is correct
7 Correct 5 ms 13144 KB Output is correct
8 Correct 5 ms 13144 KB Output is correct
9 Correct 53 ms 13264 KB Output is correct
10 Correct 4 ms 13144 KB Output is correct
11 Correct 4 ms 13148 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 4 ms 13144 KB Output is correct
14 Correct 5 ms 13144 KB Output is correct
15 Correct 3 ms 12888 KB Output is correct
16 Correct 2 ms 12888 KB Output is correct
17 Correct 297 ms 45280 KB Output is correct
18 Correct 268 ms 43968 KB Output is correct
19 Correct 299 ms 43460 KB Output is correct
20 Correct 299 ms 43716 KB Output is correct
21 Correct 301 ms 44224 KB Output is correct
22 Correct 358 ms 44224 KB Output is correct
23 Correct 296 ms 44480 KB Output is correct
24 Correct 387 ms 55716 KB Output is correct
25 Execution timed out 1032 ms 55748 KB Time limit exceeded
26 Halted 0 ms 0 KB -