Submission #821790

#	Time	Username	Problem	Language	Result	Execution time	Memory
821790		annabeth9680	Parachute rings (IOI12_rings)	C++17	100 / 100	1399 ms	125252 KiB

rings

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+20;
int N,cnt,casenum,cycnum,cycl,deg[MAXN],ha[MAXN],hb[MAXN];
vector<int> adj[MAXN];
struct dsu{
    int rep[MAXN],sz[MAXN];
    void init(int n){
        for(int i = 0;i<n;++i){
            rep[i] = i;
            sz[i] = 1;
        }
    }
    int gro(int x){
        return sz[finden(x)];
    }
    int finden(int x){
        return (rep[x] = (rep[x] == x) ? x : finden(rep[x]));
    }
    bool unite(int x, int y){
        x = finden(x); y = finden(y);
        if(x == y) return false;
        sz[y] += sz[x]; rep[x] = y;
        return true;
    }
}DSU;
struct fall{
    dsu D; int deg[MAXN]; bool ok = true; int u;
    void init(int u){
        fall::u = u;
        D.init(N); fill(deg,deg+N,0);
        for(int i = 0;i<cnt;++i){
            int a = ha[i], b = hb[i];
            if(a == u || b == u) continue;
            deg[a]++; deg[b]++;
            if(!D.unite(a,b)){
                ok = false;
            }
            if(deg[a] >= 3 || deg[b] >= 3){
                ok = false;
            }
        }
    }
    void link(){
        int i = cnt-1;
        int a = ha[i], b = hb[i];
        if(a == u || b == u) return;
        deg[a]++; deg[b]++;
        if(!D.unite(a,b)){
            ok = false;
        }
        if(deg[a] >= 3 || deg[b] >= 3){
            ok = false;
        }
    }
    bool check(){
        return ok;
    }
}falls[4];
void Init(int n){
    N = n;
    DSU.init(N);
}
bool f = false;
void Link(int a, int b){
    ha[cnt] = a; hb[cnt] = b; deg[a]++; deg[b]++; cnt++;
    adj[a].push_back(b); adj[b].push_back(a);
    if(f){
        for(int i = 0;i<casenum;++i) falls[i].link();
        return;
    }
    int u = -1;
    if(deg[a] >= 3) u = a;
    if(deg[b] >= 3) u = b;
    if(u == -1){
        if(!DSU.unite(a,b)){
            cycnum++;
            cycl += DSU.gro(a);
        }
        return;
    }
    f = true;
    falls[casenum++].init(u);
    for(auto v : adj[u]){
        falls[casenum++].init(v);
    }
}
int CountCritical(){
    if(f){
        int ans = 0;
        for(int i = 0;i<casenum;++i){
            if(falls[i].check()){
                ans++;
            }
        }
        return ans;
    }
    if(cycnum >= 2) return 0;
    if(cycnum == 1) return cycl;
    return N;
}

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