oj.uz

답안 #589384

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589384 2022-07-04T14:26:52 Z TheScrasse 낙하산 고리들 (IOI12_rings) C++17
38 / 100
 4000 ms 213492 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});
    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[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

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 211600 KB Output is correct
2 Correct 790 ms 212288 KB Output is correct
3 Correct 916 ms 212088 KB Output is correct
4 Correct 279 ms 211652 KB Output is correct
5 Correct 552 ms 211704 KB Output is correct
6 Correct 879 ms 211972 KB Output is correct
7 Correct 277 ms 211784 KB Output is correct
8 Correct 695 ms 211848 KB Output is correct
9 Correct 922 ms 212592 KB Output is correct
10 Correct 919 ms 212596 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4074 ms 213064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 211600 KB Output is correct
2 Correct 790 ms 212288 KB Output is correct
3 Correct 916 ms 212088 KB Output is correct
4 Correct 279 ms 211652 KB Output is correct
5 Correct 552 ms 211704 KB Output is correct
6 Correct 879 ms 211972 KB Output is correct
7 Correct 277 ms 211784 KB Output is correct
8 Correct 695 ms 211848 KB Output is correct
9 Correct 922 ms 212592 KB Output is correct
10 Correct 919 ms 212596 KB Output is correct
11 Correct 934 ms 212652 KB Output is correct
12 Correct 1625 ms 213480 KB Output is correct
13 Correct 1665 ms 213316 KB Output is correct
14 Correct 1111 ms 211916 KB Output is correct
15 Correct 1046 ms 212068 KB Output is correct
16 Correct 1583 ms 212172 KB Output is correct
17 Correct 1623 ms 213304 KB Output is correct
18 Correct 1606 ms 212868 KB Output is correct
19 Correct 1560 ms 212176 KB Output is correct
20 Correct 1583 ms 213492 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 211600 KB Output is correct
2 Correct 790 ms 212288 KB Output is correct
3 Correct 916 ms 212088 KB Output is correct
4 Correct 279 ms 211652 KB Output is correct
5 Correct 552 ms 211704 KB Output is correct
6 Correct 879 ms 211972 KB Output is correct
7 Correct 277 ms 211784 KB Output is correct
8 Correct 695 ms 211848 KB Output is correct
9 Correct 922 ms 212592 KB Output is correct
10 Correct 919 ms 212596 KB Output is correct
11 Correct 934 ms 212652 KB Output is correct
12 Correct 1625 ms 213480 KB Output is correct
13 Correct 1665 ms 213316 KB Output is correct
14 Correct 1111 ms 211916 KB Output is correct
15 Correct 1046 ms 212068 KB Output is correct
16 Correct 1583 ms 212172 KB Output is correct
17 Correct 1623 ms 213304 KB Output is correct
18 Correct 1606 ms 212868 KB Output is correct
19 Correct 1560 ms 212176 KB Output is correct
20 Correct 1583 ms 213492 KB Output is correct
21 Correct 3915 ms 213364 KB Output is correct
22 Execution timed out 4078 ms 213204 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 211600 KB Output is correct
2 Correct 790 ms 212288 KB Output is correct
3 Correct 916 ms 212088 KB Output is correct
4 Correct 279 ms 211652 KB Output is correct
5 Correct 552 ms 211704 KB Output is correct
6 Correct 879 ms 211972 KB Output is correct
7 Correct 277 ms 211784 KB Output is correct
8 Correct 695 ms 211848 KB Output is correct
9 Correct 922 ms 212592 KB Output is correct
10 Correct 919 ms 212596 KB Output is correct
11 Execution timed out 4074 ms 213064 KB Time limit exceeded
12 Halted 0 ms 0 KB -