oj.uz

Submission #23673

# Submission time Handle Problem Language Result Execution time Memory
23673 2017-05-18T23:18:10 Z Hiasat Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 124580 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

vector< pii > g[150001];

int dp[150001][2][31];
int last[150001][2][31];
int mx[150001][2][31];

ll need[150001][2][2];

void bld(int N, int P, int state) {
	memset(dp, -1, sizeof dp);
	memset(last,-1,sizeof last);
	memset(mx, 0, sizeof mx);
	for (int i = 0 ; i < N ; i++) {
		if (g[i].size()) {
			dp[i][0][0] = dp[i][1][0] = g[i][0].first;
			last[i][0][0] = last[i][1][0] = g[i][0].second;
			if (g[i][0].first == P) {
				if (state == 0) {
					mx[i][0][0] = g[P][0].second != g[i][0].second;
				} else {
					mx[i][0][0] = g[P][0].second == g[i][0].second;
				}

			}
		}
		if (g[i].size() > 1) {
			dp[i][1][0] =  g[i][1].first;
			last[i][1][0] = g[i][1].second;
			if (g[i][1].first == P) {
				if (state == 0) {
					mx[i][1][0] = g[P][0].second != g[i][1].second;
				} else {
					mx[i][1][0] = g[P][0].second == g[i][1].second;
				}
			}
		}
	}
	for (int k = 1 ; k <= 30; k++)
		for (int i = 0 ; i < N ; i++) {
			for (int it = 0 ; it < 2 ; it++) {
				if (dp[i][it][k - 1] != -1) {
					int vv = dp[i][it][k - 1];
					int uu = last[i][it][k - 1];
					dp[i][it][k] = dp[vv][(g[vv][0].second == uu)][k - 1];
					last[i][it][k] = last[vv][(g[vv][0].second == uu)][k - 1];
					mx[i][it][k] = max(mx[i][it][k - 1], mx[vv][(g[vv][0].second == uu)][k - 1]);
				}
			}
		}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	for (int i = 0; i < M; ++i) {
		g[R[i][0]].push_back(make_pair(R[i][1], i));
		g[R[i][1]].push_back(make_pair(R[i][0], i));
	}
	memset(need, -1, sizeof need);
	
	for (int state = 0 ; state < 2 ; state++) {
		bld(N, P, state);
		for (int i = 0 ; i < N ; i++) {
			for (int it = 0 ; it < 2 ; it++) {
				int go = i;
				int lastEdge = -1;
				if (it && g[i].size())
					lastEdge = g[i][0].second;
				ll t = 0;
				for (int k = 30 ; k >= 0 ; k--) {
					if (!mx[go][lastEdge == g[go][0].second][k]) {
						t += (1 << k);
						int nw = dp[go][lastEdge == g[go][0].second][k];
						lastEdge = last[go][lastEdge == g[go][0].second][k];
						go = nw;
					}
				}
				if (dp[go][lastEdge == g[go][0].second][0] == P) {
					need[i][it][state] = t + 1;
				}
			}
		}
	}
	for (int i = 0 ; i < Q ; i++) {
		int cnt = 0;
		for (int j = 0 ; j < N ; j++) {
			for (int state = 0 ; state < 2 ; state++) {
				if (need[j][0][state] == -1)
					continue;
				if (G[i] < need[j][0][state])
					continue;
				ll rem = G[i] - need[j][0][state];
				if(rem == 0){

					cnt++;
					break;
				} else if (need[P][state][state] != -1 && rem%need[P][state][state] == 0){
					cnt++;
					break;
				}
			}
		}
		answer(cnt);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 117748 KB Output is correct
2 Correct 140 ms 117852 KB Output is correct
3 Correct 128 ms 117760 KB Output is correct
4 Correct 122 ms 117796 KB Output is correct
5 Correct 123 ms 117884 KB Output is correct
6 Correct 151 ms 117876 KB Output is correct
7 Correct 163 ms 117828 KB Output is correct
8 Correct 156 ms 117844 KB Output is correct
9 Correct 127 ms 118032 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 117748 KB Output is correct
2 Correct 140 ms 117852 KB Output is correct
3 Correct 128 ms 117760 KB Output is correct
4 Correct 122 ms 117796 KB Output is correct
5 Correct 123 ms 117884 KB Output is correct
6 Correct 151 ms 117876 KB Output is correct
7 Correct 163 ms 117828 KB Output is correct
8 Correct 156 ms 117844 KB Output is correct
9 Correct 127 ms 118032 KB Output is correct
10 Correct 123 ms 117696 KB Output is correct
11 Correct 479 ms 118792 KB Output is correct
12 Correct 766 ms 120060 KB Output is correct
13 Correct 1217 ms 121136 KB Output is correct
14 Correct 1437 ms 124180 KB Output is correct
15 Correct 1500 ms 124412 KB Output is correct
16 Correct 1513 ms 123592 KB Output is correct
17 Correct 873 ms 123416 KB Output is correct
18 Correct 559 ms 120008 KB Output is correct
19 Correct 1445 ms 124176 KB Output is correct
20 Correct 1390 ms 124400 KB Output is correct
21 Correct 1313 ms 123480 KB Output is correct
22 Correct 875 ms 123172 KB Output is correct
23 Correct 3798 ms 124580 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 117748 KB Output is correct
2 Correct 140 ms 117852 KB Output is correct
3 Correct 128 ms 117760 KB Output is correct
4 Correct 122 ms 117796 KB Output is correct
5 Correct 123 ms 117884 KB Output is correct
6 Correct 151 ms 117876 KB Output is correct
7 Correct 163 ms 117828 KB Output is correct
8 Correct 156 ms 117844 KB Output is correct
9 Correct 127 ms 118032 KB Output is correct
10 Correct 123 ms 117696 KB Output is correct
11 Correct 479 ms 118792 KB Output is correct
12 Correct 766 ms 120060 KB Output is correct
13 Correct 1217 ms 121136 KB Output is correct
14 Correct 1437 ms 124180 KB Output is correct
15 Correct 1500 ms 124412 KB Output is correct
16 Correct 1513 ms 123592 KB Output is correct
17 Correct 873 ms 123416 KB Output is correct
18 Correct 559 ms 120008 KB Output is correct
19 Correct 1445 ms 124176 KB Output is correct
20 Correct 1390 ms 124400 KB Output is correct
21 Correct 1313 ms 123480 KB Output is correct
22 Correct 875 ms 123172 KB Output is correct
23 Correct 3798 ms 124580 KB Output is correct
24 Correct 123 ms 117700 KB Output is correct
25 Correct 575 ms 118748 KB Output is correct
26 Correct 911 ms 120028 KB Output is correct
27 Execution timed out 5050 ms 121148 KB Time limit exceeded
28 Halted 0 ms 0 KB -