Submission #16392

#	Time	Username	Problem	Language	Result	Execution time	Memory
16392		comet	Parachute rings (IOI12_rings)	C++98	100 / 100	1922 ms	90564 KiB

rings

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pb push_back
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
int N,mode;
mat path;
int degree[4][1000000];
struct disjoint{
    vec p;
	void init(int n){
		p=vec(n);
        for(int i=0;i<n;i++)p[i]=i;
    }
    int find(int x){
        int v=x;
        while(p[v]!=v)v=p[v];
        while(p[x]!=x){
            p[x]=v;
            x=p[x];
        }
        return v;
    }
    bool merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return 0;
        p[x]=y;
        return 1;
    }
}A,z[4];
bool CircleChk[1000000],chk[4];
int cnt,Ex[4];

void Init(int n){
    N=n;
    A.init(n);
    path.assign(n,vec(0));
}

int CountCritical(){
    // Base
    if(mode==0){
        return N;
    }

    // Circle
    else if(mode==1){
        return cnt;
    }

    // Divided
    else if(mode==2){
        cnt=0;
        for(int k=0;k<4;k++)if(!chk[k])cnt++;
        if(cnt==0)mode=-1;

        /*puts("mode 2");
        for(int i=0;i<4;i++)printf("%d ",chk[i]);
        puts("");*/

        return cnt;
    }

    // End
    else{
        return 0;
    }
}

void CircleBfs(int v){
	queue<int> Q;
    Q.push(v);
    CircleChk[v]=1;
    while(!Q.empty()){
        v=Q.front();
        cnt++;
        Q.pop();
        for(int i=0;i<path[v].size();i++){
          	int u=path[v][i];
            if(!CircleChk[u]){
                Q.push(u);
                CircleChk[u]=1;
            }
        }
    }
}

void make_graph(int x,int k){
	
    Ex[k]=x;
    z[k].init(N);

    for(int i=0;i<N;i++){
        if(x==i)continue;

		int ok=0;
        for(int j=0;j<path[i].size();j++){
			if(path[i][j]==x)
				ok=1;
			else
				z[k].merge(i,path[i][j]);
        }
				
		degree[k][i]=path[i].size()-ok;

        if(degree[k][i]>2){
            chk[k]=1;
            return;
        }
    }
}

void Link(int x,int y){
    // Base
    if(mode==0){
        path[x].pb(y);
        path[y].pb(x);
        if(path[x].size()<path[y].size())swap(x,y);
        if(path[y].size()>2){
			mode=-1;
			return;
        }

        if(path[x].size()>2){
            mode=2;
            for(int i=0;i<3;i++)
                make_graph(path[x][i],i);
            make_graph(x,3);
            return;
        }

        if(!A.merge(x,y)){
            cnt=0;
            mode=1;
            CircleBfs(x);
        }
    }

    // Circle
    else if(mode==1){
        path[x].pb(y);
        path[y].pb(x);
        if(!A.merge(x,y)){
            mode=-1;
            return;
        }
        if(path[x].size()<path[y].size())swap(x,y);
        if(path[y].size()>2){
			mode=-1;
			return;
        }

        if(path[x].size()>2){
            if(CircleChk[x]==0&&CircleChk[y]==0){
                mode=-1;
                return;
            }
            mode=2;
            for(int i=0;i<3;i++){
				if(!CircleChk[path[x][i]]){
					chk[i]=1;
					continue;
				}
                make_graph(path[x][i],i);
            }
            make_graph(x,3);
            return;
        }
    }

    // Divided
    else if(mode==2){
		path[x].pb(y);
		path[y].pb(x);
        for(int k=0;k<4;k++){
            if(chk[k])continue;
            if(Ex[k]==x||Ex[k]==y)continue;
            degree[k][x]++;
            degree[k][y]++;
            if(!z[k].merge(x,y))chk[k]=1;
            if(degree[k][x]<degree[k][y])swap(x,y);
            if(degree[k][x]>2)chk[k]=1;
        }
		cnt=0;
		for(int k=0;k<4;k++)
			if(!chk[k])cnt++;

		if(cnt==0)mode=-1;
    }

    // End
    else{
        return;
    }
}

Compilation message (stderr)

rings.cpp: In function 'void CircleBfs(int)':
rings.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<path[v].size();i++){
                     ~^~~~~~~~~~~~~~~
rings.cpp: In function 'void make_graph(int, int)':
rings.cpp:98:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(x==i)continue;
         ^~
rings.cpp:100:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   int ok=0;
   ^~~
rings.cpp:101:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<path[i].size();j++){
                     ~^~~~~~~~~~~~~~~

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