Submission #806677

#	Time	Username	Problem	Language	Result	Execution time	Memory
806677		QwertyPi	Parachute rings (IOI12_rings)	C++14	100 / 100	1455 ms	134936 KiB

rings

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 11;
int N, M;
int deg[MAXN], a[MAXN], b[MAXN];
vector<int> G[MAXN];

struct DSU{
    int dsu[MAXN], sz[MAXN];
    void init(int n){
        for(int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
    }
    int f(int x){
        return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
    }
    int size(int x){
        return sz[f(x)];
    }
    bool g(int x, int y){
        x = f(x), y = f(y); if(x == y) return false;
        dsu[x] = y; sz[y] += sz[x]; return true;
    }
} dsu;

struct Case{
    int v; DSU dsu; bool ok; int deg[MAXN];
    void init(int v){
        Case::v = v;
        ok = true; dsu.init(N);
        fill(deg, deg + N, 0);
        for(int i = 0; i < M; i++){
            if(a[i] == v || b[i] == v) continue;
            deg[a[i]]++; deg[b[i]]++;
            if(deg[a[i]] >= 3 || deg[b[i]] >= 3)
                ok = false;
            if(!dsu.g(a[i], b[i]))
                ok = false;
        }
    };
    void link(){
        int i = M - 1;
        if(a[i] == v || b[i] == v) return;
        deg[a[i]]++; deg[b[i]]++;
        if(deg[a[i]] >= 3 || deg[b[i]] >= 3)
            ok = false;
        if(!dsu.g(a[i], b[i]))
            ok = false;
    }
    bool isCritical(){
        return ok;
    }
} cases[4];

int caseCount = 0;

void Init(int N_) {
    N = N_; dsu.init(N);
}

bool byCase = false;
int cycleCount = 0, cycleLength = 0;
void Link(int A, int B) {
    deg[A]++; deg[B]++; a[M] = A, b[M] = B, M++;
    G[A].push_back(B); G[B].push_back(A);

    if(byCase){
        for(int i = 0; i < caseCount; i++) cases[i].link();
        return;
    }

    int v = -1; if(deg[A] >= 3) v = A; if(deg[B] >= 3) v = B;
    
    if(v == -1){
        bool b = dsu.g(A, B);
        if(!b) cycleCount++, cycleLength += dsu.size(A);
        return;
    }

    byCase = true;
    cases[caseCount++].init(v);
    for(auto u : G[v]){
        cases[caseCount++].init(u);
    }
}

int CountCritical() {
    int ans = 0;
    if(byCase){
        for(int i = 0; i < caseCount; i++) ans += cases[i].isCritical();
    }else{
        if(cycleCount >= 2) ans = 0;
        else if(cycleCount == 1) ans = cycleLength;
        else ans = N;
    }
    return ans;
}

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