Submission #1196985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196985		Hamed_Ghaffari	Parachute rings (IOI12_rings)	C++20	100 / 100	966 ms	125640 KiB

rings

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define SZ(x) int(x.size())

const int MXN = 1e6+5;

int n;

struct DSU {
    int par[MXN], sz[MXN], deg[MXN];
    bool bad, lst;
    DSU() {
        iota(par, par+n, 0);
        fill(sz, sz+n, 1);
        fill(deg, deg+n, 0);
        bad = 0;
        lst = 0;
    }
    int find(int v) { return v==par[v] ? v : par[v]=find(par[v]); }
    bool add(int u, int v) {
        int uu = find(u), vv = find(v);
        if(lst) {
            if(uu==vv) return 1;
        }
        else if(bad || deg[u]==2 || deg[v]==2 || uu==vv) {
            bad = 1;
            return uu==vv;
        }
        deg[u]++;
        deg[v]++;
        if(sz[uu]<sz[vv]) swap(uu, vv);
        sz[par[vv]=uu] += sz[vv];
        return 0;
    }
} dsu[5];

void Init(int n) {
    ::n = n;
    for(int i=0; i<5; i++) dsu[i] = DSU();
    dsu[4].lst = 1;
}

bool step2;
int ver[4], cyc_size, cnt_cyc;
vector<int> g[MXN];

void add(int i, int u, int v) {
    if(u==ver[i] || v==ver[i]) return;
    dsu[i].add(u, v);
}

void gostep2() {
    step2 = 1;
    for(int i=0; i<4; i++)
        for(int u=0; u<n; u++)
            for(int v : g[u])
                if(u<v)
                    add(i, u, v);
}

void Link(int u, int v) {
    if(step2) {
        for(int i=0; i<4; i++)
            add(i, u, v);
    }
    else {
        g[u].push_back(v);
        g[v].push_back(u);
        if(SZ(g[u])==3) {
            ver[0] = u;
            for(int i=0; i<3; i++)
                ver[i+1] = g[u][i];
            gostep2();
        }
        else if(SZ(g[v])==3) {
            ver[0] = v;
            for(int i=0; i<3; i++)
                ver[i+1] = g[v][i];
            gostep2();
        }
        else {
            if(dsu[4].add(u, v)) {
                cyc_size = dsu[4].sz[dsu[4].find(u)];
                cnt_cyc++;
            }
        }
    }
}

int CountCritical() {
    if(step2) {
        int ans = 0;
        for(int i=0; i<4; i++)
            if(!dsu[i].bad)
                ans++;
        return ans;
    }
    if(!cnt_cyc) return n;
    if(cnt_cyc==1) return cyc_size;
    return 0;
}

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