Submission #1022691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022691		vjudge1	Parachute rings (IOI12_rings)	C++17	100 / 100	724 ms	139180 KiB

rings

#define L 1<<20
#include<bits/stdc++.h>
using namespace std;
struct union_find{
    int par[L],sz[L];
    union_find(){
        memset(par,0,sizeof par);
        for(auto&i:sz)i=1;
    }
    int abp(int n){
        return par[n]?par[n]=abp(par[n]):n;
    }
    bool merge(int a,int b){
        a=abp(a);b=abp(b);
        if(a-b) par[a]=b,
            sz[b]+=sz[a];
        return a-b;
    }
} global;
struct whatthehellisthis{
    union_find a_union_find;
    int ok,deg[L];
    whatthehellisthis(){ok=1;memset(deg,0,sizeof deg);}
    void AE(int a,int b){
        ok&=a_union_find.merge(a,b);
        ok&=max(++deg[a],++deg[b])<3;
    }
} thgy[4];
int N,FAIL,deg[L];
vector<int>adj[L];
int stage2,cycsz;
int mp[L];
vector<pair<int,int>>sofar;
set<int>st;
void Init(int N_) {
    N = N_;
    cycsz=N;
}
int C;
void Link(int A, int B) {
    if(stage2){ for(auto i:st)
        if(A-i&&B-i) thgy[mp[i]].AE(A,B);
    }else {
        sofar.push_back({A,B});
        deg[A]++; deg[B]++;
        adj[A].push_back(B);
        adj[B].push_back(A);
        if(deg[A]>deg[B])
            swap(A,B);
        if(deg[B]==3){
            stage2=1;
            st.insert(B);
            for(auto i:adj[B])
                st.insert(i),mp[i]=++C;
            for(auto i:st) for(auto[x,y]:sofar)
                if(i-x&&i-y) thgy[mp[i]].AE(x,y);
        } else if(!global.merge(A,B)){
            if(cycsz-N) FAIL=1;
            else cycsz=global.sz[global.abp(A)];
        }
    }
}
int CountCritical() {
    if(FAIL)return 0;
    if(stage2){
        int ans=0;
        for(auto i:st)
            ans+=thgy[mp[i]].ok;
        return ans;
    } else return cycsz;
}

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