oj.uz

Submission #850464

# Submission time Handle Problem Language Result Execution time Memory
850464 2023-09-16T15:11:39 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(x);
        }
    }
    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 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 8 ms 12888 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 4 ms 8796 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8800 KB Output is correct
2 Correct 2 ms 8800 KB Output is correct
3 Correct 403 ms 23200 KB Output is correct
4 Correct 214 ms 22468 KB Output is correct
5 Correct 276 ms 22860 KB Output is correct
6 Correct 339 ms 24068 KB Output is correct
7 Correct 314 ms 23344 KB Output is correct
8 Correct 268 ms 22060 KB Output is correct
9 Correct 200 ms 22456 KB Output is correct
10 Execution timed out 1049 ms 22608 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 8796 KB Output is correct
2 Correct 250 ms 22612 KB Output is correct
3 Correct 231 ms 21180 KB Output is correct
4 Correct 198 ms 21412 KB Output is correct
5 Correct 171 ms 21956 KB Output is correct
6 Correct 242 ms 21184 KB Output is correct
7 Correct 148 ms 22660 KB Output is correct
8 Correct 166 ms 23068 KB Output is correct
9 Correct 104 ms 21232 KB Output is correct
10 Correct 177 ms 22212 KB Output is correct
11 Correct 189 ms 22964 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 420 ms 23720 KB Output is correct
3 Correct 306 ms 23576 KB Output is correct
4 Correct 295 ms 23128 KB Output is correct
5 Correct 211 ms 22264 KB Output is correct
6 Correct 214 ms 23072 KB Output is correct
7 Runtime error 797 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 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 8 ms 12888 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 4 ms 8796 KB Output is correct
15 Correct 2 ms 8800 KB Output is correct
16 Correct 2 ms 8800 KB Output is correct
17 Correct 403 ms 23200 KB Output is correct
18 Correct 214 ms 22468 KB Output is correct
19 Correct 276 ms 22860 KB Output is correct
20 Correct 339 ms 24068 KB Output is correct
21 Correct 314 ms 23344 KB Output is correct
22 Correct 268 ms 22060 KB Output is correct
23 Correct 200 ms 22456 KB Output is correct
24 Execution timed out 1049 ms 22608 KB Time limit exceeded
25 Halted 0 ms 0 KB -