Submission #7709

#	Time	Username	Problem	Language	Result	Execution time	Memory
7709		baneling100	Parachute rings (IOI12_rings)	C++98	100 / 100	1955 ms	110172 KiB

rings

#include <algorithm>
#include <vector>

using namespace std;

typedef pair <int,int> ppair;
vector <int> Ring[1000000];
vector <ppair> Line;
int N, Three, Anc[1000000][4], Cycle[4], Deg[1000000][4], Size[1000000][4], MaxDeg[4], CycleSize, Die[4];

void Init(int N_) {

    int i;

    N = N_;
    for(i=0 ; i<N ; i++) {
        Size[i][0]=Size[i][1]=Size[i][2]=Size[i][3]=1;
        Anc[i][0]=Anc[i][1]=Anc[i][2]=Anc[i][3]=-1;
    }
}

int FindAnc(int X, int Y) {

    int Father, Temp;

    Father=X;
    while(Anc[Father][Y]>=0) {
        Father=Anc[Father][Y];
    }
    while(Anc[X][Y]>=0) {
        Temp=Anc[X][Y];
        Anc[X][Y]=Father;
        X=Temp;
    }
    return Father;
}

void DivideThree(int X) {

    int i, j=Line.size(), k, P, Q;

    for(i=0 ; i<N ; i++) {
        Anc[i][0]=-1;
        Deg[i][0]=0;
        Size[i][0]=1;
    }
    Cycle[0]=0;
    Die[0]=X;
    for(i=0 ; i<j ; i++)
        if(Line[i].first!=X && Line[i].second!=X) {
            Deg[Line[i].first][0]++;
            Deg[Line[i].second][0]++;
            if(MaxDeg[0]<Deg[Line[i].first][0])
                MaxDeg[0]=Deg[Line[i].first][0];
            if(MaxDeg[0]<Deg[Line[i].second][0])
                MaxDeg[0]=Deg[Line[i].second][0];
            P=FindAnc(Line[i].first,0);
            Q=FindAnc(Line[i].second,0);
            if(P<Q) {
                Anc[Q][0]=P;
                Size[P][0]+=Size[Q][0];
                Size[Q][0]=0;
            }
            else if(P>Q) {
                Anc[P][0]=Q;
                Size[Q][0]+=Size[P][0];
                Size[P][0]=0;
            }
            else
                Cycle[0]++;
        }
    for(k=0 ; k<3 ; k++) {
        Die[k+1]=Ring[X][k];
        for(i=0 ; i<j ; i++)
            if(Line[i].first!=Ring[X][k] && Line[i].second!=Ring[X][k]) {
                Deg[Line[i].first][k+1]++;
                Deg[Line[i].second][k+1]++;
                if(MaxDeg[k+1]<Deg[Line[i].first][k+1])
                    MaxDeg[k+1]=Deg[Line[i].first][k+1];
                if(MaxDeg[k+1]<Deg[Line[i].second][k+1])
                    MaxDeg[k+1]=Deg[Line[i].second][k+1];
                P=FindAnc(Line[i].first,k+1);
                Q=FindAnc(Line[i].second,k+1);
                if(P<Q) {
                    Anc[Q][k+1]=P;
                    Size[P][k+1]+=Size[Q][k+1];
                    Size[Q][k+1]=0;
                }
                else if(P>Q) {
                    Anc[P][k+1]=Q;
                    Size[Q][k+1]+=Size[P][k+1];
                    Size[P][k+1]=0;
                }
                else
                    Cycle[k+1]++;
            }
    }
}

void Link(int A, int B) {

    int i, X, Y;

    Ring[A].push_back(B);
    Ring[B].push_back(A);
    Line.push_back(make_pair(A,B));
    if(Three)
        for(i=0 ; i<4 ; i++) {
            if(A!=Die[i] && B!=Die[i]) {
                Deg[A][i]++;
                Deg[B][i]++;
                if(MaxDeg[i]<Deg[A][i])
                    MaxDeg[i]=Deg[A][i];
                if(MaxDeg[i]<Deg[B][i])
                    MaxDeg[i]=Deg[B][i];
                X=FindAnc(A,i);
                Y=FindAnc(B,i);
                if(X<Y) {
                    Anc[Y][i]=X;
                    Size[X][i]+=Size[Y][i];
                    Size[Y][i]=0;
                }
                else if(X>Y) {
                    Anc[X][i]=Y;
                    Size[Y][i]+=Size[X][i];
                    Size[X][i]=0;
                }
                else
                    Cycle[i]++;
            }
        }
    else {
        Deg[A][0]++;
        Deg[B][0]++;
        X=FindAnc(A,0);
        Y=FindAnc(B,0);
        if(X<Y) {
            Anc[Y][0]=X;
            Size[X][0]+=Size[Y][0];
            Size[Y][0]=0;
        }
        else if(X>Y) {
            Anc[X][0]=Y;
            Size[Y][0]+=Size[X][0];
            Size[X][0]=0;
        }
        else {
            Cycle[0]++;
            CycleSize=Size[X][0];
        }
        if(Deg[A][0]>=3) {
            DivideThree(A);
            Three=1;
        }
        else if(Deg[B][0]>=3) {
            DivideThree(B);
            Three=1;
        }
    }
}

int CountCritical(void) {

    int i, Cnt=0;

    if(Three) {
        for(i=0 ; i<4 ; i++)
            if(MaxDeg[i]<=2 && !Cycle[i])
                Cnt++;
        return Cnt;
    }
    else {
        if(Cycle[0]==0)
            return N;
        else if(Cycle[0]==1)
            return CycleSize;
        else
            return 0;
    }
}

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