oj.uz

Submission #347845

# Submission time Handle Problem Language Result Execution time Memory
347845 2021-01-13T15:25:44 Z tengiz05 Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 44908 KB 
#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
const int N_ = 150005;
int ans, n, m, target;
vector<int> edges[N_];
int d;
int nxt[N_*2][30];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	target = P;
	n = N, m = M;
	for(int i=0;i<m;i++){
		if(edges[R[i][0]].size() < 2)edges[R[i][0]].pb(R[i][1]);
		if(edges[R[i][1]].size() < 2)edges[R[i][1]].pb(R[i][0]);
	}
	for(int i=0;i<n*2;i++){
		nxt[i][0] = -1;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<(int)edges[i].size();j++){
			int to = edges[i][j];
			if(edges[to][0] == i && edges[to].size() == 2){
				nxt[i+j*n][0] = to+n;
			}else {
				nxt[i+j*n][0] = to;
			}
		}
	}
	for(int i=1;i<30;i++){
		for(int u=0;u<n*2;u++){
			if(~nxt[u][0])nxt[u][i] = nxt[nxt[u][i-1]][i-1];
			else nxt[u][i] = -1;
		}
	}
	for(int q=0;q<Q;q++){
		int t = G[q];
		int ans = 0;
		for(int i=0;i<n;i++){
			int s = i;
			if(nxt[i][0] == -1)continue;
			for(int j=0;j<30;j++){
				if((1<<j)&t)s = nxt[s][j];
			}ans += (s == P || s == P+n);
		}answer(ans);
	}return;
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4076 KB Output is correct
2 Correct 3 ms 4076 KB Output is correct
3 Correct 3 ms 4076 KB Output is correct
4 Correct 3 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 3 ms 3820 KB Output is correct
8 Correct 4 ms 4076 KB Output is correct
9 Correct 4 ms 4204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4076 KB Output is correct
2 Correct 3 ms 4076 KB Output is correct
3 Correct 3 ms 4076 KB Output is correct
4 Correct 3 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 3 ms 3820 KB Output is correct
8 Correct 4 ms 4076 KB Output is correct
9 Correct 4 ms 4204 KB Output is correct
10 Correct 4 ms 3948 KB Output is correct
11 Correct 20 ms 9964 KB Output is correct
12 Correct 45 ms 14316 KB Output is correct
13 Correct 112 ms 27372 KB Output is correct
14 Correct 184 ms 40940 KB Output is correct
15 Correct 182 ms 41412 KB Output is correct
16 Correct 136 ms 29292 KB Output is correct
17 Correct 113 ms 25324 KB Output is correct
18 Correct 50 ms 14316 KB Output is correct
19 Correct 183 ms 40940 KB Output is correct
20 Correct 187 ms 41452 KB Output is correct
21 Correct 130 ms 29292 KB Output is correct
22 Correct 114 ms 25424 KB Output is correct
23 Correct 227 ms 44908 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4076 KB Output is correct
2 Correct 3 ms 4076 KB Output is correct
3 Correct 3 ms 4076 KB Output is correct
4 Correct 3 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 3 ms 3820 KB Output is correct
8 Correct 4 ms 4076 KB Output is correct
9 Correct 4 ms 4204 KB Output is correct
10 Correct 4 ms 3948 KB Output is correct
11 Correct 20 ms 9964 KB Output is correct
12 Correct 45 ms 14316 KB Output is correct
13 Correct 112 ms 27372 KB Output is correct
14 Correct 184 ms 40940 KB Output is correct
15 Correct 182 ms 41412 KB Output is correct
16 Correct 136 ms 29292 KB Output is correct
17 Correct 113 ms 25324 KB Output is correct
18 Correct 50 ms 14316 KB Output is correct
19 Correct 183 ms 40940 KB Output is correct
20 Correct 187 ms 41452 KB Output is correct
21 Correct 130 ms 29292 KB Output is correct
22 Correct 114 ms 25424 KB Output is correct
23 Correct 227 ms 44908 KB Output is correct
24 Correct 15 ms 3948 KB Output is correct
25 Correct 4327 ms 10096 KB Output is correct
26 Execution timed out 5049 ms 14916 KB Time limit exceeded
27 Halted 0 ms 0 KB -