oj.uz

Submission #18672

# Submission time Handle Problem Language Result Execution time Memory
18672 2016-02-14T02:13:38 Z suhgyuho_william Parachute rings (IOI12_rings) C++
20 / 100
 4000 ms 63364 KB 
#include <vector>
#include <stdio.h>
#include <queue>

using namespace std;

int N;
vector<int> edge[1000010];
bool check[1000010],flag;
int q[1000010],top,rear;

int jj;
void dfs2(int x,int par){
    int i,v,cnt = 0;

    check[x] = true;
    for(i=0; i<edge[x].size(); i++){
        v = edge[x][i];
        if(v == par || v == jj) continue;
        if(check[v]){ flag = false; continue; }
        dfs2(v,x);
        cnt++;
    }
    if(cnt >= 2) flag = false;
}

int checking(int x){
	int i,t,v;

	jj = x;
	for(i=1; i<=N; i++) check[i] = false;
	flag = true; check[jj] = true;
	for(i=1; i<=N; i++){
		if(!check[i]){
			t = 0;
			for(int k=0; k<edge[i].size(); k++){
				v = edge[i][k];
				if(v == jj) continue;
				t++;
				if(t == 3){
					flag = false;
					break;
				}
				dfs2(v,i);
			}
		}
		if(!flag) break;
	}
	if(flag) return 1;
	else return 0;
}

void Init(int N_) {
	N = N_;
}

void Link(int A, int B) {
	A++; B++;
	edge[A].push_back(B);
	edge[B].push_back(A);
}

int problem;
void dfs(int x,int par){
    int i,v,cnt = 0;

    check[x] = true;
    for(i=0; i<edge[x].size(); i++){
        v = edge[x][i];
        if(v == par) continue;
        if(check[v]){
			flag = false;
			problem = x;
			continue;
		}
        dfs(v,x);
        cnt++;
    }
    if(cnt >= 2){
		flag = false;
		problem = x;
    }
}
int ischain(int x){
	int i,t;

	check[x] = true; t = 0; flag = true;
	for(i=0; i<edge[x].size(); i++){
		t++;
        if(!check[edge[x][i]]) dfs(edge[x][i],x);
	}
	if(t >= 3){
		flag = false;
		problem = x;
	}
	if(flag) return 0; // chain
	else return 1;
}

int CountCritical() {
	int i,j,cnt,s,v;
	int ans = 0;

	cnt = 0;
	for(i=1; i<=N; i++) check[i] = false;
	for(i=1; i<=N; i++){
		if(!check[i]){
			if(ischain(i) == 1){
				cnt++;
				s = i;
			}
		}
	}
	if(cnt >= 2) return 0;
	if(cnt == 0) return N;
	for(i=1; i<=N; i++) check[i] = false;
	cnt = edge[s].size();
	if(cnt > 3){
		ans += checking(s);
		return ans;
	}else if(cnt == 3){
        ans += checking(s);
        for(i=0; i<edge[s].size(); i++){
			v = edge[s][i];
			ans += checking(v);
        }
        return ans;
	}else{
		i = ischain(s);
		s = problem;
		//printf("problem : %d\n",problem);
		ans += checking(s);
		if(edge[s].size() > 3) return ans;
		for(i=0; i<edge[s].size(); i++){
			v = edge[s][i];
			ans += checking(v);
		}
	}
	ans = 0;
	for(i=1; i<=N; i++) ans += checking(i);
	return ans;
}

Compilation message

rings.cpp: In function 'void dfs2(int, int)':
rings.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<edge[x].size(); i++){
              ~^~~~~~~~~~~~~~~
rings.cpp: In function 'int checking(int)':
rings.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<edge[i].size(); k++){
                 ~^~~~~~~~~~~~~~~
rings.cpp: In function 'void dfs(int, int)':
rings.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<edge[x].size(); i++){
              ~^~~~~~~~~~~~~~~
rings.cpp: In function 'int ischain(int)':
rings.cpp:88:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<edge[x].size(); i++){
           ~^~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:123:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<edge[s].size(); i++){
                  ~^~~~~~~~~~~~~~~
rings.cpp:134:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<edge[s].size(); i++){
            ~^~~~~~~~~~~~~~~
rings.cpp:101:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,cnt,s,v;
        ^
rings.cpp:129:5: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   i = ischain(s);
   ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 25 ms 24192 KB Output is correct
3 Correct 25 ms 24192 KB Output is correct
4 Correct 31 ms 24192 KB Output is correct
5 Correct 227 ms 24192 KB Output is correct
6 Correct 1016 ms 24636 KB Output is correct
7 Correct 22 ms 24636 KB Output is correct
8 Correct 23 ms 24636 KB Output is correct
9 Correct 530 ms 24636 KB Output is correct
10 Correct 160 ms 24636 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 40976 KB Output is correct
2 Correct 1187 ms 50292 KB Output is correct
3 Correct 1203 ms 63364 KB Output is correct
4 Execution timed out 4011 ms 63364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 25 ms 24192 KB Output is correct
3 Correct 25 ms 24192 KB Output is correct
4 Correct 31 ms 24192 KB Output is correct
5 Correct 227 ms 24192 KB Output is correct
6 Correct 1016 ms 24636 KB Output is correct
7 Correct 22 ms 24636 KB Output is correct
8 Correct 23 ms 24636 KB Output is correct
9 Correct 530 ms 24636 KB Output is correct
10 Correct 160 ms 24636 KB Output is correct
11 Execution timed out 4094 ms 63364 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 25 ms 24192 KB Output is correct
3 Correct 25 ms 24192 KB Output is correct
4 Correct 31 ms 24192 KB Output is correct
5 Correct 227 ms 24192 KB Output is correct
6 Correct 1016 ms 24636 KB Output is correct
7 Correct 22 ms 24636 KB Output is correct
8 Correct 23 ms 24636 KB Output is correct
9 Correct 530 ms 24636 KB Output is correct
10 Correct 160 ms 24636 KB Output is correct
11 Execution timed out 4094 ms 63364 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 25 ms 24192 KB Output is correct
3 Correct 25 ms 24192 KB Output is correct
4 Correct 31 ms 24192 KB Output is correct
5 Correct 227 ms 24192 KB Output is correct
6 Correct 1016 ms 24636 KB Output is correct
7 Correct 22 ms 24636 KB Output is correct
8 Correct 23 ms 24636 KB Output is correct
9 Correct 530 ms 24636 KB Output is correct
10 Correct 160 ms 24636 KB Output is correct
11 Correct 507 ms 40976 KB Output is correct
12 Correct 1187 ms 50292 KB Output is correct
13 Correct 1203 ms 63364 KB Output is correct
14 Execution timed out 4011 ms 63364 KB Time limit exceeded
15 Halted 0 ms 0 KB -