oj.uz

Submission #18673

# Submission time Handle Problem Language Result Execution time Memory
18673 2016-02-14T02:17:17 Z suhgyuho_william Parachute rings (IOI12_rings) C++
20 / 100
 4000 ms 63236 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;
			if(problem == -1) problem = x;
			continue;
		}
        dfs(v,x);
        cnt++;
    }
    if(cnt >= 2){
		flag = false;
		if(problem == -1) 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;
	}
	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{
		problem = -1;
		i = ischain(s);
		s = problem;
		//printf("problem : %d\n",problem-1);
		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:122: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:100: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 20 ms 23800 KB Output is correct
2 Correct 23 ms 24060 KB Output is correct
3 Correct 25 ms 24120 KB Output is correct
4 Correct 28 ms 24120 KB Output is correct
5 Correct 228 ms 24176 KB Output is correct
6 Correct 1002 ms 24448 KB Output is correct
7 Correct 22 ms 24448 KB Output is correct
8 Correct 25 ms 24448 KB Output is correct
9 Correct 536 ms 24448 KB Output is correct
10 Correct 179 ms 24448 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 40980 KB Output is correct
2 Correct 1284 ms 50128 KB Output is correct
3 Correct 1122 ms 63236 KB Output is correct
4 Execution timed out 4025 ms 63236 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 23 ms 24060 KB Output is correct
3 Correct 25 ms 24120 KB Output is correct
4 Correct 28 ms 24120 KB Output is correct
5 Correct 228 ms 24176 KB Output is correct
6 Correct 1002 ms 24448 KB Output is correct
7 Correct 22 ms 24448 KB Output is correct
8 Correct 25 ms 24448 KB Output is correct
9 Correct 536 ms 24448 KB Output is correct
10 Correct 179 ms 24448 KB Output is correct
11 Execution timed out 4013 ms 63236 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 23 ms 24060 KB Output is correct
3 Correct 25 ms 24120 KB Output is correct
4 Correct 28 ms 24120 KB Output is correct
5 Correct 228 ms 24176 KB Output is correct
6 Correct 1002 ms 24448 KB Output is correct
7 Correct 22 ms 24448 KB Output is correct
8 Correct 25 ms 24448 KB Output is correct
9 Correct 536 ms 24448 KB Output is correct
10 Correct 179 ms 24448 KB Output is correct
11 Execution timed out 4013 ms 63236 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 23 ms 24060 KB Output is correct
3 Correct 25 ms 24120 KB Output is correct
4 Correct 28 ms 24120 KB Output is correct
5 Correct 228 ms 24176 KB Output is correct
6 Correct 1002 ms 24448 KB Output is correct
7 Correct 22 ms 24448 KB Output is correct
8 Correct 25 ms 24448 KB Output is correct
9 Correct 536 ms 24448 KB Output is correct
10 Correct 179 ms 24448 KB Output is correct
11 Correct 509 ms 40980 KB Output is correct
12 Correct 1284 ms 50128 KB Output is correct
13 Correct 1122 ms 63236 KB Output is correct
14 Execution timed out 4025 ms 63236 KB Time limit exceeded
15 Halted 0 ms 0 KB -