oj.uz

Submission #382363

# Submission time Handle Problem Language Result Execution time Memory
382363 2021-03-27T07:28:19 Z ParsaAlizadeh Parachute rings (IOI12_rings) C++17
100 / 100
 1349 ms 87892 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
//#define endl            '\n'

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 1e6 + 10;

int n, mark[N], par[N], sz[N], ans = -1, vgt2;
vector<int> adj[N];
vector<pii> E;

struct TmpDSU {
    int flag = true, u, par[N];

    TmpDSU() {
        fill(par, par + N, -1);
    }

    int find(int u) {
        return (this->par[u] == -1 ? u : this->par[u] = find(this->par[u]));
    }

    void merge(int u, int v) {
        if (!flag || u == this->u || v == this->u)
            return;
        u = find(u), v = find(v);
        if (u == v) {
            flag = false;
            return;
        }
        if (v < u) swap(u, v);
        this->par[v] = u;
    }
} tmpdsu[4];

int dsufind(int u) {
    return (par[u] == -1 ? u : par[u] = dsufind(par[u]));
}

void dsumerge(int u, int v) {
    u = dsufind(u), v = dsufind(v);
    if (u == v) {
        if (!vgt2)
            ans = (ans != -1 ? 0 : sz[u]);
        return;
    }
    if (sz[v] > sz[u])
        swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
}

void apply(int u) {
    if (adj[u].size() <= 2)
        return;
    if (vgt2) {
        for (int i = 0; i < 4; i++) {
            bool f = tmpdsu[i].u == u;
            if (adj[u].size() == 3)
            for (int v : adj[u])
                f |= tmpdsu[i].u == v;
            tmpdsu[i].flag &= f;
        }
        return;
    }
    vgt2 = 1;
    assert(adj[u].size() == 3);
    tmpdsu[0].u = u;
    for (int i = 0; i < 3; i++)
        tmpdsu[i + 1].u = adj[u][i];
    for (auto &e : E) {
        for (int i = 0; i < 4; i++) 
            tmpdsu[i].merge(e.X, e.Y);
    }
}

void Init(int N_) {
    n = N_;
    fill(par, par + n, -1);
    fill(sz, sz + n, 1);
}

void Link(int u, int v) {
    E.emplace_back(u, v);
    adj[u].push_back(v);
    adj[v].push_back(u);

    if (vgt2)
    for (int i = 0; i < 4; i++) {
        tmpdsu[i].merge(u, v);
    }

    dsumerge(u, v);
    apply(u);
    apply(v);
}

int CountCritical() {
    if (!vgt2)
        return (ans == -1 ? n : ans);
    int t = 0;
    for (int i = 0; i < 4; i++)
        t += tmpdsu[i].flag;
    return t;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39532 KB Output is correct
2 Correct 29 ms 39660 KB Output is correct
3 Correct 29 ms 39788 KB Output is correct
4 Correct 27 ms 39532 KB Output is correct
5 Correct 28 ms 39660 KB Output is correct
6 Correct 29 ms 39788 KB Output is correct
7 Correct 28 ms 39532 KB Output is correct
8 Correct 28 ms 39660 KB Output is correct
9 Correct 29 ms 39788 KB Output is correct
10 Correct 29 ms 39804 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 63956 KB Output is correct
2 Correct 947 ms 77000 KB Output is correct
3 Correct 1000 ms 81996 KB Output is correct
4 Correct 1068 ms 86344 KB Output is correct
5 Correct 1080 ms 86472 KB Output is correct
6 Correct 1041 ms 85196 KB Output is correct
7 Correct 981 ms 81268 KB Output is correct
8 Correct 1256 ms 83412 KB Output is correct
9 Correct 1349 ms 86600 KB Output is correct
10 Correct 707 ms 84304 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39532 KB Output is correct
2 Correct 29 ms 39660 KB Output is correct
3 Correct 29 ms 39788 KB Output is correct
4 Correct 27 ms 39532 KB Output is correct
5 Correct 28 ms 39660 KB Output is correct
6 Correct 29 ms 39788 KB Output is correct
7 Correct 28 ms 39532 KB Output is correct
8 Correct 28 ms 39660 KB Output is correct
9 Correct 29 ms 39788 KB Output is correct
10 Correct 29 ms 39804 KB Output is correct
11 Correct 29 ms 39788 KB Output is correct
12 Correct 32 ms 40044 KB Output is correct
13 Correct 33 ms 40092 KB Output is correct
14 Correct 30 ms 39916 KB Output is correct
15 Correct 30 ms 39916 KB Output is correct
16 Correct 31 ms 40044 KB Output is correct
17 Correct 31 ms 40044 KB Output is correct
18 Correct 33 ms 40300 KB Output is correct
19 Correct 31 ms 40172 KB Output is correct
20 Correct 32 ms 40172 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39532 KB Output is correct
2 Correct 29 ms 39660 KB Output is correct
3 Correct 29 ms 39788 KB Output is correct
4 Correct 27 ms 39532 KB Output is correct
5 Correct 28 ms 39660 KB Output is correct
6 Correct 29 ms 39788 KB Output is correct
7 Correct 28 ms 39532 KB Output is correct
8 Correct 28 ms 39660 KB Output is correct
9 Correct 29 ms 39788 KB Output is correct
10 Correct 29 ms 39804 KB Output is correct
11 Correct 29 ms 39788 KB Output is correct
12 Correct 32 ms 40044 KB Output is correct
13 Correct 33 ms 40092 KB Output is correct
14 Correct 30 ms 39916 KB Output is correct
15 Correct 30 ms 39916 KB Output is correct
16 Correct 31 ms 40044 KB Output is correct
17 Correct 31 ms 40044 KB Output is correct
18 Correct 33 ms 40300 KB Output is correct
19 Correct 31 ms 40172 KB Output is correct
20 Correct 32 ms 40172 KB Output is correct
21 Correct 46 ms 41320 KB Output is correct
22 Correct 57 ms 42596 KB Output is correct
23 Correct 69 ms 43492 KB Output is correct
24 Correct 76 ms 42596 KB Output is correct
25 Correct 42 ms 40940 KB Output is correct
26 Correct 68 ms 43748 KB Output is correct
27 Correct 77 ms 44640 KB Output is correct
28 Correct 72 ms 44640 KB Output is correct
29 Correct 62 ms 42728 KB Output is correct
30 Correct 87 ms 45280 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39532 KB Output is correct
2 Correct 29 ms 39660 KB Output is correct
3 Correct 29 ms 39788 KB Output is correct
4 Correct 27 ms 39532 KB Output is correct
5 Correct 28 ms 39660 KB Output is correct
6 Correct 29 ms 39788 KB Output is correct
7 Correct 28 ms 39532 KB Output is correct
8 Correct 28 ms 39660 KB Output is correct
9 Correct 29 ms 39788 KB Output is correct
10 Correct 29 ms 39804 KB Output is correct
11 Correct 442 ms 63956 KB Output is correct
12 Correct 947 ms 77000 KB Output is correct
13 Correct 1000 ms 81996 KB Output is correct
14 Correct 1068 ms 86344 KB Output is correct
15 Correct 1080 ms 86472 KB Output is correct
16 Correct 1041 ms 85196 KB Output is correct
17 Correct 981 ms 81268 KB Output is correct
18 Correct 1256 ms 83412 KB Output is correct
19 Correct 1349 ms 86600 KB Output is correct
20 Correct 707 ms 84304 KB Output is correct
21 Correct 29 ms 39788 KB Output is correct
22 Correct 32 ms 40044 KB Output is correct
23 Correct 33 ms 40092 KB Output is correct
24 Correct 30 ms 39916 KB Output is correct
25 Correct 30 ms 39916 KB Output is correct
26 Correct 31 ms 40044 KB Output is correct
27 Correct 31 ms 40044 KB Output is correct
28 Correct 33 ms 40300 KB Output is correct
29 Correct 31 ms 40172 KB Output is correct
30 Correct 32 ms 40172 KB Output is correct
31 Correct 46 ms 41320 KB Output is correct
32 Correct 57 ms 42596 KB Output is correct
33 Correct 69 ms 43492 KB Output is correct
34 Correct 76 ms 42596 KB Output is correct
35 Correct 42 ms 40940 KB Output is correct
36 Correct 68 ms 43748 KB Output is correct
37 Correct 77 ms 44640 KB Output is correct
38 Correct 72 ms 44640 KB Output is correct
39 Correct 62 ms 42728 KB Output is correct
40 Correct 87 ms 45280 KB Output is correct
41 Correct 236 ms 56936 KB Output is correct
42 Correct 555 ms 71252 KB Output is correct
43 Correct 279 ms 54372 KB Output is correct
44 Correct 669 ms 87892 KB Output is correct
45 Correct 741 ms 80852 KB Output is correct
46 Correct 687 ms 84940 KB Output is correct
47 Correct 931 ms 85352 KB Output is correct
48 Correct 506 ms 71508 KB Output is correct
49 Correct 683 ms 83784 KB Output is correct
50 Correct 743 ms 83468 KB Output is correct
51 Correct 308 ms 55548 KB Output is correct
52 Correct 605 ms 79048 KB Output is correct
53 Correct 502 ms 72428 KB Output is correct
54 Correct 1079 ms 82876 KB Output is correct
55 Correct 1050 ms 85628 KB Output is correct