oj.uz

Submission #850471

# Submission time Handle Problem Language Result Execution time Memory
850471 2023-09-16T15:27:26 Z MinaRagy06 Stranded Far From Home (BOI22_island) C++17
25 / 100
 1000 ms 55476 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;
        }
        if (adj[node].empty() || val < (*adj[node].begin())[0]) {
            bad[node] = 1;
            continue;
        }
        int x = (*adj[node].begin())[1];
        x = find(x).first;
        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 2 ms 12888 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 5 ms 13148 KB Output is correct
5 Correct 4 ms 13144 KB Output is correct
6 Correct 5 ms 13148 KB Output is correct
7 Correct 5 ms 13144 KB Output is correct
8 Correct 5 ms 13144 KB Output is correct
9 Correct 52 ms 13144 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 13144 KB Output is correct
13 Correct 4 ms 13144 KB Output is correct
14 Correct 5 ms 13304 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 300 ms 45508 KB Output is correct
4 Correct 262 ms 44028 KB Output is correct
5 Correct 278 ms 43812 KB Output is correct
6 Correct 302 ms 43936 KB Output is correct
7 Correct 304 ms 44480 KB Output is correct
8 Correct 336 ms 45164 KB Output is correct
9 Correct 275 ms 44796 KB Output is correct
10 Correct 343 ms 55248 KB Output is correct
11 Execution timed out 1051 ms 55476 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 12892 KB Output is correct
2 Correct 310 ms 44232 KB Output is correct
3 Correct 332 ms 45932 KB Output is correct
4 Correct 239 ms 43812 KB Output is correct
5 Correct 235 ms 43888 KB Output is correct
6 Correct 336 ms 45052 KB Output is correct
7 Correct 198 ms 44736 KB Output is correct
8 Correct 199 ms 45504 KB Output is correct
9 Correct 112 ms 44736 KB Output is correct
10 Correct 257 ms 45336 KB Output is correct
11 Correct 279 ms 44992 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 428 ms 45088 KB Output is correct
3 Correct 387 ms 45504 KB Output is correct
4 Correct 416 ms 45692 KB Output is correct
5 Correct 374 ms 43968 KB Output is correct
6 Correct 394 ms 44740 KB Output is correct
7 Execution timed out 1039 ms 55476 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 2 ms 12888 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 5 ms 13148 KB Output is correct
5 Correct 4 ms 13144 KB Output is correct
6 Correct 5 ms 13148 KB Output is correct
7 Correct 5 ms 13144 KB Output is correct
8 Correct 5 ms 13144 KB Output is correct
9 Correct 52 ms 13144 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 13144 KB Output is correct
13 Correct 4 ms 13144 KB Output is correct
14 Correct 5 ms 13304 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 300 ms 45508 KB Output is correct
18 Correct 262 ms 44028 KB Output is correct
19 Correct 278 ms 43812 KB Output is correct
20 Correct 302 ms 43936 KB Output is correct
21 Correct 304 ms 44480 KB Output is correct
22 Correct 336 ms 45164 KB Output is correct
23 Correct 275 ms 44796 KB Output is correct
24 Correct 343 ms 55248 KB Output is correct
25 Execution timed out 1051 ms 55476 KB Time limit exceeded
26 Halted 0 ms 0 KB -