oj.uz

Submission #736146

# Submission time Handle Problem Language Result Execution time Memory
736146 2023-05-05T09:05:36 Z DAleksa Stranded Far From Home (BOI22_island) C++17
25 / 100
 399 ms 37552 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);
                sz[V] = 0;
                can[V].clear();
            }
        }
        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 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 182 ms 34284 KB Output is correct
4 Correct 255 ms 36872 KB Output is correct
5 Correct 303 ms 33756 KB Output is correct
6 Correct 340 ms 34384 KB Output is correct
7 Correct 307 ms 34360 KB Output is correct
8 Correct 339 ms 34512 KB Output is correct
9 Correct 225 ms 34444 KB Output is correct
10 Correct 151 ms 35052 KB Output is correct
11 Correct 294 ms 35164 KB Output is correct
12 Correct 253 ms 34348 KB Output is correct
13 Correct 241 ms 37488 KB Output is correct
14 Correct 237 ms 36828 KB Output is correct
15 Correct 206 ms 34316 KB Output is correct
16 Correct 189 ms 34108 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 350 ms 34256 KB Output is correct
3 Correct 399 ms 34428 KB Output is correct
4 Correct 283 ms 37548 KB Output is correct
5 Correct 257 ms 37552 KB Output is correct
6 Correct 366 ms 34424 KB Output is correct
7 Correct 249 ms 34468 KB Output is correct
8 Correct 287 ms 34560 KB Output is correct
9 Correct 158 ms 34228 KB Output is correct
10 Correct 239 ms 34412 KB Output is correct
11 Correct 271 ms 34568 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 272 ms 34292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -