oj.uz

Submission #850467

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

const int N = 200'005;
int par[N], sz[N], bad[N];
ll cnt[N], a[N];
vector<int> 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 nxt : adj[v]) {
        int x = find(nxt).first;
        if (x != u) {
            adj[u].push_back(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].push_back(v);
        adj[v].push_back(u);
    }
    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 nxt : adj[node]) {
            if (find(nxt).first != node && val >= a[nxt]) {
                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 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct
9 Correct 6 ms 12888 KB Output is correct
10 Correct 3 ms 8792 KB Output is correct
11 Correct 3 ms 8792 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 3 ms 8792 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 336 ms 24248 KB Output is correct
4 Correct 191 ms 22976 KB Output is correct
5 Correct 251 ms 22908 KB Output is correct
6 Correct 257 ms 23224 KB Output is correct
7 Correct 277 ms 23348 KB Output is correct
8 Correct 228 ms 22476 KB Output is correct
9 Correct 177 ms 22456 KB Output is correct
10 Execution timed out 1045 ms 23104 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 255 ms 21444 KB Output is correct
3 Correct 211 ms 21188 KB Output is correct
4 Correct 172 ms 22316 KB Output is correct
5 Correct 172 ms 22360 KB Output is correct
6 Correct 236 ms 23064 KB Output is correct
7 Correct 147 ms 20928 KB Output is correct
8 Correct 152 ms 22100 KB Output is correct
9 Correct 97 ms 21700 KB Output is correct
10 Correct 182 ms 22976 KB Output is correct
11 Correct 185 ms 22252 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 398 ms 24400 KB Output is correct
3 Correct 291 ms 24080 KB Output is correct
4 Correct 244 ms 23776 KB Output is correct
5 Correct 222 ms 22192 KB Output is correct
6 Correct 225 ms 23144 KB Output is correct
7 Runtime error 773 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct
9 Correct 6 ms 12888 KB Output is correct
10 Correct 3 ms 8792 KB Output is correct
11 Correct 3 ms 8792 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 3 ms 8792 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct
15 Correct 2 ms 8792 KB Output is correct
16 Correct 2 ms 8792 KB Output is correct
17 Correct 336 ms 24248 KB Output is correct
18 Correct 191 ms 22976 KB Output is correct
19 Correct 251 ms 22908 KB Output is correct
20 Correct 257 ms 23224 KB Output is correct
21 Correct 277 ms 23348 KB Output is correct
22 Correct 228 ms 22476 KB Output is correct
23 Correct 177 ms 22456 KB Output is correct
24 Execution timed out 1045 ms 23104 KB Time limit exceeded
25 Halted 0 ms 0 KB -