Submission #817683

#	Time	Username	Problem	Language	Result	Execution time	Memory
817683		annabeth9680	Parachute rings (IOI12_rings)	C++17	0 / 100	1489 ms	134948 KiB

rings

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

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