Submission #1035281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035281		thinknoexit	Parachute rings (IOI12_rings)	C++17	100 / 100	604 ms	118332 KiB

rings

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000001;
vector<int> adj[N];
int U_i[N], V_i[N];
int small_case, cycle, gg, tot;
int deg[N], p[N], sz[N];
int n, ans;
class solve {
private:
    int deg[N], p[N];
    int fr(int i) {
        return p[i] == i ? i : p[i] = fr(p[i]);
    }
public:
    int root, ans;
    void Link(int A, int B) {
        if (!ans) return;
        if (A == root || B == root) return;
        if (++deg[A] == 3 || ++deg[B] == 3) {
            ans = 0;
            return;
        }
        int pa = fr(A), pb = fr(B);
        if (pa == pb) {
            ans = 0;
            return;
        }
        p[pb] = pa;
    }
    void init() {
        ans = 1;
        for (int i = 0;i < n;i++) p[i] = i;
        for (int i = 0;i < tot;i++) {
            Link(U_i[i], V_i[i]);
        }
    }
} U[4];
int fr(int i) {
    return p[i] == i ? i : p[i] = fr(p[i]);
}
void Init(int N_) {
    n = N_;
    ans = n;
    for (int i = 0;i < n;i++) p[i] = i, sz[i] = 1;
}

void Link(int A, int B) {
    U_i[tot] = A, V_i[tot] = B, tot++;
    if (gg) return;
    if (small_case) {
        for (int i = 0;i < 4;i++) U[i].Link(A, B);
        return;
    }
    adj[A].push_back(B);
    adj[B].push_back(A);
    if (++deg[A] == 3) {
        small_case = 1;
        U[0].root = A;
        int idx = 1;
        for (auto& x : adj[A]) U[idx++].root = x;
    }
    if (++deg[B] == 3) {
        small_case = 1;
        U[0].root = B;
        int idx = 1;
        for (auto& x : adj[B]) U[idx++].root = x;
    }
    if (small_case) {
        for (int i = 0;i < 4;i++) U[i].init();
        return;
    }
    int pa = fr(A), pb = fr(B);
    if (pa == pb) {
        if (!cycle) ans = sz[pa], cycle = 1;
        else gg = 1;
    }
    else sz[pa] += sz[pb], p[pb] = pa;
}

int CountCritical() {
    if (gg) return 0;
    if (!small_case) return ans;
    return U[0].ans + U[1].ans + U[2].ans + U[3].ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31