oj.uz

Submission #23615

# Submission time Handle Problem Language Result Execution time Memory
23615 2017-05-15T22:31:03 Z Hiasat Tropical Garden (IOI11_garden) C++14
49 / 100
 844 ms 116004 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]) {
					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;
			long long two = 0;
			for (int it = 0 ; it < 2; ++it){
				two += need[P][curIt].first;
				curIt = need[P][curIt].second;
			}
			rem = rem%two;
			while(rem >= need[P][curIt].first){
				rem -= need[P][curIt].first;
				curIt = need[P][curIt].second;
			}
			if(rem == 0)
				cnt++;
		}
		answer(cnt);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 43000 KB Output is correct
2 Correct 40 ms 43128 KB Output is correct
3 Correct 40 ms 43100 KB Output is correct
4 Correct 38 ms 42672 KB Output is correct
5 Correct 38 ms 42560 KB Output is correct
6 Correct 38 ms 43128 KB Output is correct
7 Correct 37 ms 42616 KB Output is correct
8 Correct 39 ms 43128 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 39 ms 43000 KB Output is correct
2 Correct 40 ms 43128 KB Output is correct
3 Correct 40 ms 43100 KB Output is correct
4 Correct 38 ms 42672 KB Output is correct
5 Correct 38 ms 42560 KB Output is correct
6 Correct 38 ms 43128 KB Output is correct
7 Correct 37 ms 42616 KB Output is correct
8 Correct 39 ms 43128 KB Output is correct
9 Correct 43 ms 43356 KB Output is correct
10 Correct 39 ms 42628 KB Output is correct
11 Correct 201 ms 54568 KB Output is correct
12 Correct 375 ms 63116 KB Output is correct
13 Correct 667 ms 87344 KB Output is correct
14 Correct 844 ms 114840 KB Output is correct
15 Correct 753 ms 116004 KB Output is correct
16 Correct 684 ms 93252 KB Output is correct
17 Incorrect 477 ms 85792 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 43000 KB Output is correct
2 Correct 40 ms 43128 KB Output is correct
3 Correct 40 ms 43100 KB Output is correct
4 Correct 38 ms 42672 KB Output is correct
5 Correct 38 ms 42560 KB Output is correct
6 Correct 38 ms 43128 KB Output is correct
7 Correct 37 ms 42616 KB Output is correct
8 Correct 39 ms 43128 KB Output is correct
9 Correct 43 ms 43356 KB Output is correct
10 Correct 39 ms 42628 KB Output is correct
11 Correct 201 ms 54568 KB Output is correct
12 Correct 375 ms 63116 KB Output is correct
13 Correct 667 ms 87344 KB Output is correct
14 Correct 844 ms 114840 KB Output is correct
15 Correct 753 ms 116004 KB Output is correct
16 Correct 684 ms 93252 KB Output is correct
17 Incorrect 477 ms 85792 KB Output isn't correct
18 Halted 0 ms 0 KB -