oj.uz

Submission #589376

# Submission time Handle Problem Language Result Execution time Memory
589376 2022-07-04T14:13:52 Z TheScrasse Parachute rings (IOI12_rings) C++17
52 / 100
 1953 ms 43308 KB 
#pragma GCC optimize("Ofast")

#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 100010

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 dg[maxn], cn3, cyc, pr[maxn], sz[maxn];
    vector<ll> adj[maxn];

    graph() {
        ll i;
        for (i = 1; i <= n; i++) {
            dg[i] = 0; 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];
    }

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

graph gr[5];

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[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});
    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[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);
            }
        }
    }
}

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 14 ms 21440 KB Output is correct
2 Correct 75 ms 22084 KB Output is correct
3 Correct 111 ms 22308 KB Output is correct
4 Correct 28 ms 21576 KB Output is correct
5 Correct 65 ms 21952 KB Output is correct
6 Correct 101 ms 22400 KB Output is correct
7 Correct 29 ms 21544 KB Output is correct
8 Correct 81 ms 22092 KB Output is correct
9 Correct 105 ms 22312 KB Output is correct
10 Correct 110 ms 22400 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 43308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21440 KB Output is correct
2 Correct 75 ms 22084 KB Output is correct
3 Correct 111 ms 22308 KB Output is correct
4 Correct 28 ms 21576 KB Output is correct
5 Correct 65 ms 21952 KB Output is correct
6 Correct 101 ms 22400 KB Output is correct
7 Correct 29 ms 21544 KB Output is correct
8 Correct 81 ms 22092 KB Output is correct
9 Correct 105 ms 22312 KB Output is correct
10 Correct 110 ms 22400 KB Output is correct
11 Correct 98 ms 22276 KB Output is correct
12 Correct 193 ms 23040 KB Output is correct
13 Correct 190 ms 22976 KB Output is correct
14 Correct 141 ms 22332 KB Output is correct
15 Correct 128 ms 22044 KB Output is correct
16 Correct 189 ms 23068 KB Output is correct
17 Correct 199 ms 23016 KB Output is correct
18 Correct 175 ms 23420 KB Output is correct
19 Correct 193 ms 23092 KB Output is correct
20 Correct 228 ms 23052 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21440 KB Output is correct
2 Correct 75 ms 22084 KB Output is correct
3 Correct 111 ms 22308 KB Output is correct
4 Correct 28 ms 21576 KB Output is correct
5 Correct 65 ms 21952 KB Output is correct
6 Correct 101 ms 22400 KB Output is correct
7 Correct 29 ms 21544 KB Output is correct
8 Correct 81 ms 22092 KB Output is correct
9 Correct 105 ms 22312 KB Output is correct
10 Correct 110 ms 22400 KB Output is correct
11 Correct 98 ms 22276 KB Output is correct
12 Correct 193 ms 23040 KB Output is correct
13 Correct 190 ms 22976 KB Output is correct
14 Correct 141 ms 22332 KB Output is correct
15 Correct 128 ms 22044 KB Output is correct
16 Correct 189 ms 23068 KB Output is correct
17 Correct 199 ms 23016 KB Output is correct
18 Correct 175 ms 23420 KB Output is correct
19 Correct 193 ms 23092 KB Output is correct
20 Correct 228 ms 23052 KB Output is correct
21 Correct 514 ms 25960 KB Output is correct
22 Correct 837 ms 29072 KB Output is correct
23 Correct 1008 ms 31344 KB Output is correct
24 Correct 1083 ms 29804 KB Output is correct
25 Correct 174 ms 22496 KB Output is correct
26 Correct 1176 ms 32880 KB Output is correct
27 Correct 1605 ms 36364 KB Output is correct
28 Correct 1735 ms 37036 KB Output is correct
29 Correct 628 ms 29428 KB Output is correct
30 Correct 1953 ms 38784 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21440 KB Output is correct
2 Correct 75 ms 22084 KB Output is correct
3 Correct 111 ms 22308 KB Output is correct
4 Correct 28 ms 21576 KB Output is correct
5 Correct 65 ms 21952 KB Output is correct
6 Correct 101 ms 22400 KB Output is correct
7 Correct 29 ms 21544 KB Output is correct
8 Correct 81 ms 22092 KB Output is correct
9 Correct 105 ms 22312 KB Output is correct
10 Correct 110 ms 22400 KB Output is correct
11 Runtime error 30 ms 43308 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -