oj.uz

Submission #5074

# Submission time Handle Problem Language Result Execution time Memory
5074 2014-02-01T21:33:37 Z cki86201 Tropical Garden (IOI11_garden) C++
69 / 100
 5000 ms 75412 KB 
#include "garden.h"
#include "gardenlib.h"

//for 69 point;

const int N_ = 150020;

int nxt[N_][2];
int up[N_][2][31][2];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	int i, j, k;
	++P;
	for(i=0;i<M;i++)R[i][0]++, R[i][1]++;
	for(i=0;i<M;i++){
		if(!nxt[R[i][0]][0])nxt[R[i][0]][0] = R[i][1];
		else if(!nxt[R[i][0]][1])nxt[R[i][0]][1] = R[i][1];
		if(!nxt[R[i][1]][0])nxt[R[i][1]][0] = R[i][0];
		else if(!nxt[R[i][1]][1])nxt[R[i][1]][1] = R[i][0];
	}
	for(i=1;i<=N;i++)
		for(j=0;j<2;j++){
			up[i][j][0][1] = nxt[i][j];
			if(nxt[nxt[i][j]][0] == i && nxt[nxt[i][j]][1])up[i][j][0][0] = 1;
		}
	for(k=1;k<31;k++)
		for(i=1;i<=N;i++)
			for(j=0;j<2;j++){
				int t = up[i][j][k-1][0];
				up[i][j][k][0] = up[up[i][j][k-1][1]][t][k-1][0];
				up[i][j][k][1] = up[up[i][j][k-1][1]][t][k-1][1];
			}
	for(i=0;i<Q;i++){
		int cnt = 0;
		for(j=1;j<=N;j++){
			int now = j, to = 0;
			for(int k=30;k>=0;k--){
				if(1<<k&G[i]){
					int save = now;
					now = up[now][to][k][1];
					to = up[save][to][k][0];
				}
			}
			if(now == P)cnt++;
		}
		answer(cnt);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 808 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 804 KB Output is correct
9 Correct 4 ms 860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 808 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 804 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 31 ms 11556 KB Output is correct
12 Correct 60 ms 19268 KB Output is correct
13 Correct 249 ms 43044 KB Output is correct
14 Correct 295 ms 68060 KB Output is correct
15 Correct 301 ms 68856 KB Output is correct
16 Correct 229 ms 46664 KB Output is correct
17 Correct 205 ms 39156 KB Output is correct
18 Correct 55 ms 19192 KB Output is correct
19 Correct 295 ms 68060 KB Output is correct
20 Correct 300 ms 68860 KB Output is correct
21 Correct 209 ms 46556 KB Output is correct
22 Correct 171 ms 39164 KB Output is correct
23 Correct 342 ms 75412 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 808 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 804 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 31 ms 11556 KB Output is correct
12 Correct 60 ms 19268 KB Output is correct
13 Correct 249 ms 43044 KB Output is correct
14 Correct 295 ms 68060 KB Output is correct
15 Correct 301 ms 68856 KB Output is correct
16 Correct 229 ms 46664 KB Output is correct
17 Correct 205 ms 39156 KB Output is correct
18 Correct 55 ms 19192 KB Output is correct
19 Correct 295 ms 68060 KB Output is correct
20 Correct 300 ms 68860 KB Output is correct
21 Correct 209 ms 46556 KB Output is correct
22 Correct 171 ms 39164 KB Output is correct
23 Correct 342 ms 75412 KB Output is correct
24 Correct 10 ms 376 KB Output is correct
25 Execution timed out 5041 ms 11660 KB Time limit exceeded
26 Halted 0 ms 0 KB -