oj.uz

Submission #736138

# Submission time Handle Problem Language Result Execution time Memory
736138 2023-05-05T09:02:03 Z DAleksa Stranded Far From Home (BOI22_island) C++17
25 / 100
 425 ms 77576 KB 
#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> par;
    int n;
    DSU(int _n) {
        n = _n;
        par.resize(n);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int find_par(int u) {
        if(u == par[u]) return par[u];
        return par[u] = find_par(par[u]);
    }
    bool check(int u, int v) { return find_par(u) == find_par(v); }
    void join(int u, int v) {
        u = find_par(u);
        v = find_par(v);
        par[v] = u;
    }
};

const int N = 2e5 + 10;
int n, m;
int a[N];
vector<int> g[N];
int order[N];
set<int> can[N];
bool done[N];
long long sz[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    iota(order + 1, order + n + 1, 1);
    sort(order + 1, order + n + 1, [&](int i, int j) { return a[i] < a[j]; });
    DSU dsu(n + 1);
    for(int i = 1; i <= n; i++) {
        can[i].insert(i);
        sz[i] = a[i];
    }
    for(int i = 1; i <= n; i++) {
        int u = order[i];
        for(int v : g[u]) {
            if(!done[v]) continue;
            int U = dsu.find_par(u);
            int V = dsu.find_par(v);
            if(sz[V] < a[u]) {
                can[V].clear();
                dsu.join(u, v);
                sz[U] += sz[V];
            } else {
                if(can[U].size() < can[V].size()) swap(U, V);
                dsu.join(U, V);
                sz[U] += sz[V];
                for(auto it = can[V].begin(); it != can[V].end(); it++) can[U].insert(*it);
            }
        }
        done[u] = true;
    }
    int comp = dsu.find_par(1);
    for(int i = 1; i <= n; i++) {
        if(can[comp].find(i) == can[comp].end()) cout << 0;
        else cout << 1;
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14388 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 10 ms 14428 KB Output is correct
4 Incorrect 11 ms 14600 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14384 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 246 ms 42136 KB Output is correct
4 Correct 385 ms 72948 KB Output is correct
5 Correct 330 ms 53836 KB Output is correct
6 Correct 331 ms 56088 KB Output is correct
7 Correct 372 ms 55620 KB Output is correct
8 Correct 344 ms 59448 KB Output is correct
9 Correct 276 ms 63900 KB Output is correct
10 Correct 165 ms 38620 KB Output is correct
11 Correct 317 ms 47940 KB Output is correct
12 Correct 288 ms 49356 KB Output is correct
13 Correct 303 ms 75052 KB Output is correct
14 Correct 302 ms 73268 KB Output is correct
15 Correct 247 ms 48192 KB Output is correct
16 Correct 200 ms 47132 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14308 KB Output is correct
2 Correct 416 ms 60608 KB Output is correct
3 Correct 412 ms 62800 KB Output is correct
4 Correct 345 ms 77576 KB Output is correct
5 Correct 316 ms 75592 KB Output is correct
6 Correct 401 ms 62560 KB Output is correct
7 Correct 271 ms 48156 KB Output is correct
8 Correct 329 ms 48108 KB Output is correct
9 Correct 201 ms 47168 KB Output is correct
10 Correct 267 ms 52204 KB Output is correct
11 Correct 315 ms 63992 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Incorrect 425 ms 41748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14388 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 10 ms 14428 KB Output is correct
4 Incorrect 11 ms 14600 KB Output isn't correct
5 Halted 0 ms 0 KB -