oj.uz

Submission #589371

# Submission time Handle Problem Language Result Execution time Memory
589371 2022-07-04T14:09:09 Z TheScrasse Parachute rings (IOI12_rings) C++17
38 / 100
 4000 ms 217080 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 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 146 ms 211636 KB Output is correct
2 Correct 815 ms 212380 KB Output is correct
3 Correct 926 ms 212600 KB Output is correct
4 Correct 287 ms 211788 KB Output is correct
5 Correct 584 ms 212164 KB Output is correct
6 Correct 846 ms 212676 KB Output is correct
7 Correct 261 ms 211796 KB Output is correct
8 Correct 710 ms 212308 KB Output is correct
9 Correct 888 ms 212600 KB Output is correct
10 Correct 959 ms 212556 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 217080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 211636 KB Output is correct
2 Correct 815 ms 212380 KB Output is correct
3 Correct 926 ms 212600 KB Output is correct
4 Correct 287 ms 211788 KB Output is correct
5 Correct 584 ms 212164 KB Output is correct
6 Correct 846 ms 212676 KB Output is correct
7 Correct 261 ms 211796 KB Output is correct
8 Correct 710 ms 212308 KB Output is correct
9 Correct 888 ms 212600 KB Output is correct
10 Correct 959 ms 212556 KB Output is correct
11 Correct 937 ms 212608 KB Output is correct
12 Correct 1644 ms 213368 KB Output is correct
13 Correct 1671 ms 213348 KB Output is correct
14 Correct 1095 ms 212772 KB Output is correct
15 Correct 1106 ms 212416 KB Output is correct
16 Correct 1678 ms 213332 KB Output is correct
17 Correct 1657 ms 213452 KB Output is correct
18 Correct 1652 ms 213936 KB Output is correct
19 Correct 1617 ms 213488 KB Output is correct
20 Correct 1709 ms 213376 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 211636 KB Output is correct
2 Correct 815 ms 212380 KB Output is correct
3 Correct 926 ms 212600 KB Output is correct
4 Correct 287 ms 211788 KB Output is correct
5 Correct 584 ms 212164 KB Output is correct
6 Correct 846 ms 212676 KB Output is correct
7 Correct 261 ms 211796 KB Output is correct
8 Correct 710 ms 212308 KB Output is correct
9 Correct 888 ms 212600 KB Output is correct
10 Correct 959 ms 212556 KB Output is correct
11 Correct 937 ms 212608 KB Output is correct
12 Correct 1644 ms 213368 KB Output is correct
13 Correct 1671 ms 213348 KB Output is correct
14 Correct 1095 ms 212772 KB Output is correct
15 Correct 1106 ms 212416 KB Output is correct
16 Correct 1678 ms 213332 KB Output is correct
17 Correct 1657 ms 213452 KB Output is correct
18 Correct 1652 ms 213936 KB Output is correct
19 Correct 1617 ms 213488 KB Output is correct
20 Correct 1709 ms 213376 KB Output is correct
21 Execution timed out 4073 ms 216256 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 211636 KB Output is correct
2 Correct 815 ms 212380 KB Output is correct
3 Correct 926 ms 212600 KB Output is correct
4 Correct 287 ms 211788 KB Output is correct
5 Correct 584 ms 212164 KB Output is correct
6 Correct 846 ms 212676 KB Output is correct
7 Correct 261 ms 211796 KB Output is correct
8 Correct 710 ms 212308 KB Output is correct
9 Correct 888 ms 212600 KB Output is correct
10 Correct 959 ms 212556 KB Output is correct
11 Execution timed out 4069 ms 217080 KB Time limit exceeded
12 Halted 0 ms 0 KB -