Submission #15614

#	Time	Username	Problem	Language	Result	Execution time	Memory
15614		gs14004	Parachute rings (IOI12_rings)	C++14	0 / 100	4037 ms	108940 KiB

rings

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
  
int n;
int deg[1000005];
int focus = -1;
bool deadend = 0;
 
int v[4];
int bad[4];

int edg;
int st[1000005], ed[1000005];

struct disj{
    int pa[1000005];
    int deg2[1000005];
    int deg3[1000005];
    int degx[1000005];
    int size[1000005];
    int without;
 
    void init(int n, int w){
        without = w;
        for(int i=0; i<=n; i++) pa[i] = i, size[i] = 1;
    }
  
    int find(int x){
        return pa[x] = (pa[x] == x ? x : find(pa[x]));
    }
  
    void uni(int p, int q){
        if(p == without || q == without) return;
        degx[p]++;
        if(degx[p] == 2){
            deg2[find(p)]++;
        }
        if(degx[p] == 3){
            deg3[find(p)]++;
        }
        degx[q]++;
        if(degx[q] == 2){
            deg2[find(q)]++;
        }
        if(degx[q] == 3){
            deg3[find(q)]++;
        }
        p = find(p); q = find(q);
        if(p == q) return;
        pa[q] = p;
        deg2[p] += deg2[q];
        deg3[p] += deg3[q];
        size[p] += size[q];
    }
 
    bool ckBad(int x){
        x = find(x);
        return (deg3[x] || (deg2[x] == size[x]));
    }
}disj, wotree[4];
  
void Init(int N){
    n = N; 
    memset(v,-1,sizeof(v));
    disj.init(n,-1);
}
 
void Link(int A, int B){
    deg[A]++, deg[B]++;
    if(deg[A] <= deg[B]){
        swap(A,B);
    }
    if(deg[A] == 3 && v[0] == -1){
        v[0] = A;
        v[1] = B;
        for(int i=0; i<edg; i++){
            if(st[i] == A || ed[i] == A){
                if(v[2] == -1){
                    if(st[i] != A) v[2] = st[i];
                    else v[2] = ed[i];
                }
                if(v[3] == -1){
                    if(st[i] != A) v[3] = st[i];
                    else v[3] = ed[i];
                    break;
                }
            }
        }
        for(int i=0; i<4; i++){
            wotree[i].init(n,v[i]);
            for(int j=0; j<edg; j++){
                disj.uni(st[j], ed[j]);
                if(wotree[i].ckBad(st[j])){
                    bad[i] = 1;
                    break;
                }
            }
        }
    }
    st[edg] = A;
    ed[edg] = B;
    edg++;
    disj.uni(A,B);
    if(v[0] == -1){
        if(disj.ckBad(A)){
            if(focus == -1){
                focus = A;
            }
            else if(disj.find(focus) != disj.find(A)){
                deadend = 1;
            }
        }
    }
    else{
        for(int i=0; i<4; i++){
            wotree[i].uni(A,B);
            if(wotree[i].ckBad(A)){
                bad[i] = 1;
            }
        }
    }
}
 
  
int CountCritical(){
    if(deadend == 1) return 0;
    if(disj.without != -1) return 1;
    else if(v[0] != -1){
        int cnt = 0;
        for(int i=0; i<4; i++){
            if(!bad[i]) cnt++;
        }
        return cnt;
    }
    else{ 
        if(focus == -1) return n;
        return disj.size[disj.find(focus)];
    }
}

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