oj.uz

Submission #18668

# Submission time Handle Problem Language Result Execution time Memory
18668 2016-02-14T01:52:22 Z suhgyuho_william Parachute rings (IOI12_rings) C++
20 / 100
 4000 ms 50068 KB 
#include <vector>

using namespace std;

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

int j;
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 == j) continue;
        if(check[v]){ flag = false; continue; }
        dfs2(v,x);
        cnt++;
    }
    if(cnt >= 2) flag = false;
}

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

	j = x;
	for(i=1; i<=N; i++) check[i] = false;
	flag = true; check[j] = 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 == j) 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);
}

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; continue; }
        dfs(v,x);
        cnt++;
    }
    if(cnt >= 2) flag = false;
}
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,cnt,s;
	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;
	}
	for(i=1; i<=N; i++){
		ans += checking(i);
	}
	return ans;
}

Compilation message

rings.cpp: In function 'void dfs2(int, int)':
rings.cpp:14: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:33: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:64: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:77: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:87:12: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int i,cnt,s;
            ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 149 ms 23924 KB Output is correct
3 Correct 497 ms 24148 KB Output is correct
4 Correct 29 ms 24148 KB Output is correct
5 Correct 247 ms 24324 KB Output is correct
6 Correct 1026 ms 24512 KB Output is correct
7 Correct 23 ms 24512 KB Output is correct
8 Correct 22 ms 24512 KB Output is correct
9 Correct 522 ms 24512 KB Output is correct
10 Correct 181 ms 24512 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 40888 KB Output is correct
2 Execution timed out 4006 ms 50068 KB Time limit exceeded
3 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 149 ms 23924 KB Output is correct
3 Correct 497 ms 24148 KB Output is correct
4 Correct 29 ms 24148 KB Output is correct
5 Correct 247 ms 24324 KB Output is correct
6 Correct 1026 ms 24512 KB Output is correct
7 Correct 23 ms 24512 KB Output is correct
8 Correct 22 ms 24512 KB Output is correct
9 Correct 522 ms 24512 KB Output is correct
10 Correct 181 ms 24512 KB Output is correct
11 Execution timed out 4010 ms 50068 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 149 ms 23924 KB Output is correct
3 Correct 497 ms 24148 KB Output is correct
4 Correct 29 ms 24148 KB Output is correct
5 Correct 247 ms 24324 KB Output is correct
6 Correct 1026 ms 24512 KB Output is correct
7 Correct 23 ms 24512 KB Output is correct
8 Correct 22 ms 24512 KB Output is correct
9 Correct 522 ms 24512 KB Output is correct
10 Correct 181 ms 24512 KB Output is correct
11 Execution timed out 4010 ms 50068 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 149 ms 23924 KB Output is correct
3 Correct 497 ms 24148 KB Output is correct
4 Correct 29 ms 24148 KB Output is correct
5 Correct 247 ms 24324 KB Output is correct
6 Correct 1026 ms 24512 KB Output is correct
7 Correct 23 ms 24512 KB Output is correct
8 Correct 22 ms 24512 KB Output is correct
9 Correct 522 ms 24512 KB Output is correct
10 Correct 181 ms 24512 KB Output is correct
11 Correct 503 ms 40888 KB Output is correct
12 Execution timed out 4006 ms 50068 KB Time limit exceeded
13 Halted 0 ms 0 KB -