oj.uz

Submission #16392

# Submission time Handle Problem Language Result Execution time Memory
16392 2015-08-22T08:27:26 Z comet Parachute rings (IOI12_rings) C++
100 / 100
 1922 ms 90564 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 884 KB Output is correct
3 Correct 5 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 5 ms 1088 KB Output is correct
6 Correct 4 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 4 ms 1088 KB Output is correct
9 Correct 5 ms 1088 KB Output is correct
10 Correct 5 ms 1088 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 31236 KB Output is correct
2 Correct 1142 ms 72828 KB Output is correct
3 Correct 373 ms 72828 KB Output is correct
4 Correct 1157 ms 72828 KB Output is correct
5 Correct 1156 ms 72828 KB Output is correct
6 Correct 1256 ms 72828 KB Output is correct
7 Correct 363 ms 72828 KB Output is correct
8 Correct 1750 ms 84836 KB Output is correct
9 Correct 1922 ms 90564 KB Output is correct
10 Correct 811 ms 90564 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 884 KB Output is correct
3 Correct 5 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 5 ms 1088 KB Output is correct
6 Correct 4 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 4 ms 1088 KB Output is correct
9 Correct 5 ms 1088 KB Output is correct
10 Correct 5 ms 1088 KB Output is correct
11 Correct 5 ms 90564 KB Output is correct
12 Correct 8 ms 90564 KB Output is correct
13 Correct 9 ms 90564 KB Output is correct
14 Correct 6 ms 90564 KB Output is correct
15 Correct 7 ms 90564 KB Output is correct
16 Correct 7 ms 90564 KB Output is correct
17 Correct 6 ms 90564 KB Output is correct
18 Correct 6 ms 90564 KB Output is correct
19 Correct 8 ms 90564 KB Output is correct
20 Correct 10 ms 90564 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 884 KB Output is correct
3 Correct 5 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 5 ms 1088 KB Output is correct
6 Correct 4 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 4 ms 1088 KB Output is correct
9 Correct 5 ms 1088 KB Output is correct
10 Correct 5 ms 1088 KB Output is correct
11 Correct 5 ms 90564 KB Output is correct
12 Correct 8 ms 90564 KB Output is correct
13 Correct 9 ms 90564 KB Output is correct
14 Correct 6 ms 90564 KB Output is correct
15 Correct 7 ms 90564 KB Output is correct
16 Correct 7 ms 90564 KB Output is correct
17 Correct 6 ms 90564 KB Output is correct
18 Correct 6 ms 90564 KB Output is correct
19 Correct 8 ms 90564 KB Output is correct
20 Correct 10 ms 90564 KB Output is correct
21 Correct 27 ms 90564 KB Output is correct
22 Correct 38 ms 90564 KB Output is correct
23 Correct 48 ms 90564 KB Output is correct
24 Correct 59 ms 90564 KB Output is correct
25 Correct 23 ms 90564 KB Output is correct
26 Correct 60 ms 90564 KB Output is correct
27 Correct 56 ms 90564 KB Output is correct
28 Correct 36 ms 90564 KB Output is correct
29 Correct 32 ms 90564 KB Output is correct
30 Correct 75 ms 90564 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 884 KB Output is correct
3 Correct 5 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 5 ms 1088 KB Output is correct
6 Correct 4 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 4 ms 1088 KB Output is correct
9 Correct 5 ms 1088 KB Output is correct
10 Correct 5 ms 1088 KB Output is correct
11 Correct 450 ms 31236 KB Output is correct
12 Correct 1142 ms 72828 KB Output is correct
13 Correct 373 ms 72828 KB Output is correct
14 Correct 1157 ms 72828 KB Output is correct
15 Correct 1156 ms 72828 KB Output is correct
16 Correct 1256 ms 72828 KB Output is correct
17 Correct 363 ms 72828 KB Output is correct
18 Correct 1750 ms 84836 KB Output is correct
19 Correct 1922 ms 90564 KB Output is correct
20 Correct 811 ms 90564 KB Output is correct
21 Correct 5 ms 90564 KB Output is correct
22 Correct 8 ms 90564 KB Output is correct
23 Correct 9 ms 90564 KB Output is correct
24 Correct 6 ms 90564 KB Output is correct
25 Correct 7 ms 90564 KB Output is correct
26 Correct 7 ms 90564 KB Output is correct
27 Correct 6 ms 90564 KB Output is correct
28 Correct 6 ms 90564 KB Output is correct
29 Correct 8 ms 90564 KB Output is correct
30 Correct 10 ms 90564 KB Output is correct
31 Correct 27 ms 90564 KB Output is correct
32 Correct 38 ms 90564 KB Output is correct
33 Correct 48 ms 90564 KB Output is correct
34 Correct 59 ms 90564 KB Output is correct
35 Correct 23 ms 90564 KB Output is correct
36 Correct 60 ms 90564 KB Output is correct
37 Correct 56 ms 90564 KB Output is correct
38 Correct 36 ms 90564 KB Output is correct
39 Correct 32 ms 90564 KB Output is correct
40 Correct 75 ms 90564 KB Output is correct
41 Correct 253 ms 90564 KB Output is correct
42 Correct 797 ms 90564 KB Output is correct
43 Correct 323 ms 90564 KB Output is correct
44 Correct 347 ms 90564 KB Output is correct
45 Correct 519 ms 90564 KB Output is correct
46 Correct 721 ms 90564 KB Output is correct
47 Correct 1018 ms 90564 KB Output is correct
48 Correct 332 ms 90564 KB Output is correct
49 Correct 714 ms 90564 KB Output is correct
50 Correct 815 ms 90564 KB Output is correct
51 Correct 343 ms 90564 KB Output is correct
52 Correct 314 ms 90564 KB Output is correct
53 Correct 301 ms 90564 KB Output is correct
54 Correct 1420 ms 90564 KB Output is correct
55 Correct 1122 ms 90564 KB Output is correct