oj.uz

Submission #589389

# Submission time Handle Problem Language Result Execution time Memory
589389 2022-07-04T14:32:24 Z TheScrasse Parachute rings (IOI12_rings) C++17
52 / 100
 1365 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll int
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e9
#define mod 998244353
#define maxn 1000010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll ms[5], status;
vector<array<ll, 2>> el;

struct graph {
    ll cn3, cyc, pr[maxn], sz[maxn];
    vector<ll> adj[maxn];

    graph() {
        ll i;
        for (i = 1; i <= n; i++) {
            pr[i] = i; sz[i] = 1;
        }
        cn3 = 0; cyc = 0;
    }

    ll find(ll x) {
        if (x == pr[x]) return x;
        return pr[x] = find(pr[x]);
    }

    bool same(ll a, ll b) {
        return (find(a) == find(b));
    }

    void onion(ll a, ll b) {
        a = find(a); b = find(b);
        if (a == b) {
            cyc++; res = sz[a]; return;
        }
        if (sz[a] < sz[b]) swap(a, b);
        pr[b] = a; sz[a] += sz[b];
    }

    ll dg(ll p) {
        return adj[p].size();
    }

    void upd(ll p, ll x) {
        cn3 -= (dg(p) >= 3);
        cn3 += (dg(p) + x >= 3);
    }
};

vector<graph> gr;

void ins(ll p, ll a, ll b) {
    if (ms[p] == a || ms[p] == b) return;
    gr[p].upd(a, 1); gr[p].upd(b, 1);
    gr[p].adj[a].pb(b); gr[p].adj[b].pb(a);
    gr[p].onion(a, b);
}

void Init(int N_) {
    n = N_;
    gr.resize(5);
    // gr[0] = graph(); gr[1] = graph(); gr[2] = graph(); gr[3] = graph(); gr[4] = graph();
}

void Link(int A, int B) {
    a = A + 1; b = B + 1;
    el.pb({a, b});
    if (status == 0) ins(0, a, b);
    else if (status == 2) ins(1, a, b);
    else for (i = 0; i <= 4; i++) ins(i, a, b);

    if (status == 0) {
        if (gr[0].dg(b) >= 3) swap(a, b);
        if (gr[0].dg(a) >= 3) {
            status = 1;
            ms[1] = a; ms[2] = gr[0].adj[a][0]; ms[3] = gr[0].adj[a][1]; ms[4] = gr[0].adj[a][2];
            gr.resize(1);
            gr.resize(5);
            // gr[1] = graph(); gr[2] = graph(); gr[3] = graph(); gr[4] = graph();
            for (auto [x, y] : el) {
                for (i = 1; i <= 4; i++) ins(i, x, y);
            }
        }
    }

    if (gr[0].dg(a) == 4 || gr[0].dg(b) == 4) status = 2;
}

int CountCritical() {
    // cout << "status =" _ status _ gr[0].cyc << nl;

    if (status == 0) {
        if (gr[0].cyc == 0) return n;
        if (gr[0].cyc == 1) return res;
        return 0;
    }

    res = 0;
    for (i = 1; i <= 4; i++) {
        if (gr[i].cyc + gr[i].cn3 == 0) res++;
    }
    return res;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117708 KB Output is correct
2 Correct 75 ms 118604 KB Output is correct
3 Correct 82 ms 118420 KB Output is correct
4 Correct 62 ms 117804 KB Output is correct
5 Correct 65 ms 118032 KB Output is correct
6 Correct 56 ms 118160 KB Output is correct
7 Correct 78 ms 118156 KB Output is correct
8 Correct 57 ms 118092 KB Output is correct
9 Correct 88 ms 118780 KB Output is correct
10 Correct 82 ms 118816 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 158404 KB Output is correct
2 Correct 1365 ms 240816 KB Output is correct
3 Correct 928 ms 194588 KB Output is correct
4 Correct 891 ms 195904 KB Output is correct
5 Correct 877 ms 195904 KB Output is correct
6 Correct 873 ms 194384 KB Output is correct
7 Correct 882 ms 195788 KB Output is correct
8 Runtime error 1046 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117708 KB Output is correct
2 Correct 75 ms 118604 KB Output is correct
3 Correct 82 ms 118420 KB Output is correct
4 Correct 62 ms 117804 KB Output is correct
5 Correct 65 ms 118032 KB Output is correct
6 Correct 56 ms 118160 KB Output is correct
7 Correct 78 ms 118156 KB Output is correct
8 Correct 57 ms 118092 KB Output is correct
9 Correct 88 ms 118780 KB Output is correct
10 Correct 82 ms 118816 KB Output is correct
11 Correct 80 ms 118784 KB Output is correct
12 Correct 82 ms 119736 KB Output is correct
13 Correct 80 ms 119652 KB Output is correct
14 Correct 76 ms 118348 KB Output is correct
15 Correct 85 ms 118780 KB Output is correct
16 Correct 61 ms 118536 KB Output is correct
17 Correct 80 ms 119756 KB Output is correct
18 Correct 84 ms 119580 KB Output is correct
19 Correct 57 ms 118612 KB Output is correct
20 Correct 84 ms 119840 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117708 KB Output is correct
2 Correct 75 ms 118604 KB Output is correct
3 Correct 82 ms 118420 KB Output is correct
4 Correct 62 ms 117804 KB Output is correct
5 Correct 65 ms 118032 KB Output is correct
6 Correct 56 ms 118160 KB Output is correct
7 Correct 78 ms 118156 KB Output is correct
8 Correct 57 ms 118092 KB Output is correct
9 Correct 88 ms 118780 KB Output is correct
10 Correct 82 ms 118816 KB Output is correct
11 Correct 80 ms 118784 KB Output is correct
12 Correct 82 ms 119736 KB Output is correct
13 Correct 80 ms 119652 KB Output is correct
14 Correct 76 ms 118348 KB Output is correct
15 Correct 85 ms 118780 KB Output is correct
16 Correct 61 ms 118536 KB Output is correct
17 Correct 80 ms 119756 KB Output is correct
18 Correct 84 ms 119580 KB Output is correct
19 Correct 57 ms 118612 KB Output is correct
20 Correct 84 ms 119840 KB Output is correct
21 Correct 67 ms 120924 KB Output is correct
22 Correct 92 ms 122744 KB Output is correct
23 Correct 84 ms 124228 KB Output is correct
24 Correct 106 ms 123448 KB Output is correct
25 Correct 84 ms 121976 KB Output is correct
26 Correct 116 ms 124260 KB Output is correct
27 Correct 97 ms 124464 KB Output is correct
28 Correct 245 ms 135732 KB Output is correct
29 Correct 109 ms 124972 KB Output is correct
30 Correct 96 ms 125568 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117708 KB Output is correct
2 Correct 75 ms 118604 KB Output is correct
3 Correct 82 ms 118420 KB Output is correct
4 Correct 62 ms 117804 KB Output is correct
5 Correct 65 ms 118032 KB Output is correct
6 Correct 56 ms 118160 KB Output is correct
7 Correct 78 ms 118156 KB Output is correct
8 Correct 57 ms 118092 KB Output is correct
9 Correct 88 ms 118780 KB Output is correct
10 Correct 82 ms 118816 KB Output is correct
11 Correct 387 ms 158404 KB Output is correct
12 Correct 1365 ms 240816 KB Output is correct
13 Correct 928 ms 194588 KB Output is correct
14 Correct 891 ms 195904 KB Output is correct
15 Correct 877 ms 195904 KB Output is correct
16 Correct 873 ms 194384 KB Output is correct
17 Correct 882 ms 195788 KB Output is correct
18 Runtime error 1046 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -