oj.uz

답안 #589369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589369 2022-07-04T14:08:27 Z TheScrasse 낙하산 고리들 (IOI12_rings) C++17
0 / 100
 151 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

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

#define INF (ll)1e18
#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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 151 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 148 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 151 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 151 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 151 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -