Submission #74261

#	Time	Username	Problem	Language	Result	Execution time	Memory
74261		imeimi2000	Parachute rings (IOI12_rings)	C++14	100 / 100	1983 ms	94588 KiB

rings

#include <vector>

using namespace std;

int n;
vector<int> edge[1000001];
int phase;
int ans;

void Init(int N) {
    n = N;
    phase = 0;
    ans = n;
}

struct _uf {
    int par[1000001];
    int sz[1000001];
    int st;
    int disactive;
    _uf() {
        for (int i = 1; i <= 1000000; ++i) sz[i] = 1;
    }
    int find(int x) {
        if (par[x]) return par[x] = find(par[x]);
        return x;
    }
    int merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return 0;
        if (sz[x] < sz[y]) swap(x, y);
        par[y] = x;
        sz[x] += sz[y];
        return 1;
    }
    void disMerge(int x, int y) {
        if (!merge(x, y)) disactive = 1;
    }
    void init(int S) {
        st = S;
        for (int i = 1; i <= n; ++i) {
            if (i == S) continue;
            for (int j : edge[i]) {
                if (j == S) continue;
                if (i < j) disMerge(i, j);
            }
        }
    }
    void off(const vector<int> &v) {
        if (disactive) return;
        for (int i : v) if (st == i) return;
        disactive = 1;
    }
} uf[5];

void changePhase(int x) {
    phase = 1;
    uf[1].init(x);
    int T = 1;
    for (int i : edge[x]) uf[++T].init(i);
}

void checkDeg(int x) {
    if (edge[x].size() < 3) return;
    vector<int> ch;
    ch.push_back(x);
    if (edge[x].size() == 3) {
        for (int i : edge[x]) ch.push_back(i);
    }
    int d = 0;
    for (int i = 1; i <= 4; ++i) {
        uf[i].off(ch);
        d += uf[i].disactive;
    }
    if (d == 4) phase = 2;
}

int cyc = 0;
void Link(int A, int B) {
    ++A; ++B;
    edge[A].push_back(B);
    edge[B].push_back(A);
    int iniPhase = phase;
    if (phase == 0) {
        if (edge[A].size() > 2) changePhase(A);
        else if (edge[B].size() > 2) changePhase(B);
        else {
            if (!uf[0].merge(A, B)) {
                if (cyc++ == 0) ans = uf[0].sz[uf[0].find(A)];
                else phase = 2;
            }
        }
    }
    if (phase == 1) checkDeg(A);
    if (phase == 1) checkDeg(B);
    if (phase == 1 && iniPhase == 1) {
        for (int i = 1; i <= 4; ++i) {
            if (A == uf[i].st || B == uf[i].st) continue;
            uf[i].disMerge(A, B);
        }
        int d = 0;
        for (int i = 1; i <= 4; ++i) d += uf[i].disactive;
        if (d == 4) phase = 2;
    }
}

int CountCritical() {
    if (phase == 0) return ans;
    if (phase == 1) {
        int ret = 0;
        for (int i = 1; i <= 4; ++i) {
            if (uf[i].disactive) continue;
            ++ret;
        }
        return ret;
    }
    return 0;
}

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