oj.uz

Submission #23614

# Submission time Handle Problem Language Result Execution time Memory
23614 2017-05-15T22:17:34 Z Hiasat Tropical Garden (IOI11_garden) C++14
49 / 100
 632 ms 87288 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

vector< pii > g[150001];

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

pii need[150001][2];

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(dp, -1, sizeof dp);
	memset(need,-1,sizeof need);
	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) {
				mx[i][0][0] = 1;
			}
		}
		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) {
				mx[i][1][0] = 1;
			}
		}
	}
	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]);
				}
			}
		}
	for (int i = 0 ; i < N ; i++) {
		for (int it = 0 ; it < 2 ; it++) {
			int go = i;
			int ll = -1;
			if(it && g[i].size())
				ll = g[i][0].second;
			int t = 0;
			for (int k = 30 ; k >= 0 ; k--) {
				if (mx[go][ll == g[go][0].second][k] == 0) {
					t += (1 << k);
					int nw = dp[go][ll == g[go][0].second][k];
					ll = last[go][ll == g[go][0].second][k];
					go = nw;
				}
			}
			if(dp[go][ll == g[go][0].second][0] == P){
				bool equal = last[go][ll == g[go][0].second][0] == g[P][0].second;
				need[i][it] = make_pair(t+1,equal);
			}
		}
	}
	for (int i = 0 ; i < Q ; i++) {
		int cnt = 0;
		for (int j = 0 ; j < N ; j++) {
			if(need[j][0].first == -1)
				continue;
			if(G[i] < need[j][0].first)
				continue;
			int rem = G[i] - need[j][0].first;
			int curIt = need[j][0].second;
			if (need[P][curIt].first != -1 &&rem%need[P][curIt].first == 0){
				cnt++;
			}
		}
		answer(cnt);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 42992 KB Output is correct
2 Correct 41 ms 43124 KB Output is correct
3 Correct 40 ms 43132 KB Output is correct
4 Correct 38 ms 42616 KB Output is correct
5 Correct 37 ms 42588 KB Output is correct
6 Correct 42 ms 43184 KB Output is correct
7 Correct 36 ms 42664 KB Output is correct
8 Correct 40 ms 43200 KB Output is correct
9 Correct 43 ms 43356 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 42992 KB Output is correct
2 Correct 41 ms 43124 KB Output is correct
3 Correct 40 ms 43132 KB Output is correct
4 Correct 38 ms 42616 KB Output is correct
5 Correct 37 ms 42588 KB Output is correct
6 Correct 42 ms 43184 KB Output is correct
7 Correct 36 ms 42664 KB Output is correct
8 Correct 40 ms 43200 KB Output is correct
9 Correct 43 ms 43356 KB Output is correct
10 Correct 38 ms 42672 KB Output is correct
11 Correct 205 ms 54620 KB Output is correct
12 Correct 392 ms 63140 KB Output is correct
13 Incorrect 632 ms 87288 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 42992 KB Output is correct
2 Correct 41 ms 43124 KB Output is correct
3 Correct 40 ms 43132 KB Output is correct
4 Correct 38 ms 42616 KB Output is correct
5 Correct 37 ms 42588 KB Output is correct
6 Correct 42 ms 43184 KB Output is correct
7 Correct 36 ms 42664 KB Output is correct
8 Correct 40 ms 43200 KB Output is correct
9 Correct 43 ms 43356 KB Output is correct
10 Correct 38 ms 42672 KB Output is correct
11 Correct 205 ms 54620 KB Output is correct
12 Correct 392 ms 63140 KB Output is correct
13 Incorrect 632 ms 87288 KB Output isn't correct
14 Halted 0 ms 0 KB -