Submission #1098787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098787		MtSaka	Parachute rings (IOI12_rings)	C++17	100 / 100	820 ms	115376 KiB

rings

#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}

struct UnionFind{
    int n;
    vector<int>par;
    vector<int>deg;
    int ma,cycle,del;
    UnionFind(){}
    UnionFind(int n_):n(n_),par(n_+1,-1),deg(n_,0),ma(0),cycle(-1),del(-1){par[n]=0;}
    int root(int v){return (par[v]<0?v:par[v]=root(par[v]));}
    void merge(int u,int v){
        if(u==del||v==del||ma>2)return;
        chmax(ma,++deg[u]);
        chmax(ma,++deg[v]); 
        u=root(u),v=root(v);
        if(u==v){
            cycle=(cycle<0?u:n);
            return;
        }
        if(par[u]>par[v])swap(u,v);
        par[u]+=par[v];
        par[v]=u;
    }
    void set_del(int d){del=d;}
    int get()const{
        if(ma>2)return 0;
        if(cycle<0)return n;
        return par[cycle];
    }
};
UnionFind uf[5];
vector<vector<int>>g;
vector<pair<int,int>>edge;
bool f=false;
int n;
void Init(int N_) {
    n=N_;
    rep(i,5)uf[i]=UnionFind(n);
    g.resize(N_);
}
void Link(int A, int B) {
    edge.eb(A,B);
    g[A].eb(B);
    g[B].eb(A);
    if(!f){
        uf[0].merge(A,B);
        if(uf[0].ma>2){
            int id=0;
            rep(i,n)if(g[i].size()==3)id=i;
            uf[1].set_del(id);
            int idx=2;
            for(auto e:g[id])uf[idx++].set_del(e);
            f=true;
            for(auto [a,b]:edge)rep(j,4)uf[j+1].merge(a,b);
        }
    }
    else{
        rep(i,4)uf[i+1].merge(A,B);
    }
}

int CountCritical() {
    if(f){
        int ans=0;
        rep(i,4)if(uf[i+1].get()>0)ans++;
        return ans;
    }
    return abs(uf[0].get());
}

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