oj.uz

Submission #23611

# Submission time Handle Problem Language Result Execution time Memory
23611 2017-05-15T21:52:38 Z Hiasat Tropical Garden (IOI11_garden) C++14
49 / 100
 645 ms 87348 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 = !it?-1: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;
			for(int it = 0 ; it < 2 ; it++){
				if(need[P][curIt].first == -1)
					break;
				if(rem >= need[P][curIt].first){
					rem -= need[P][curIt].first;
					curIt = need[P][curIt].second;
				}
			}
			if (rem%need[P][curIt].first == 0){
				cnt++;
			}
		}
		answer(cnt);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 43000 KB Output is correct
2 Correct 41 ms 43176 KB Output is correct
3 Correct 39 ms 43152 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42580 KB Output is correct
6 Correct 41 ms 43228 KB Output is correct
7 Correct 38 ms 42704 KB Output is correct
8 Correct 40 ms 43100 KB Output is correct
9 Correct 41 ms 43384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 43000 KB Output is correct
2 Correct 41 ms 43176 KB Output is correct
3 Correct 39 ms 43152 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42580 KB Output is correct
6 Correct 41 ms 43228 KB Output is correct
7 Correct 38 ms 42704 KB Output is correct
8 Correct 40 ms 43100 KB Output is correct
9 Correct 41 ms 43384 KB Output is correct
10 Correct 38 ms 42716 KB Output is correct
11 Correct 192 ms 54516 KB Output is correct
12 Correct 400 ms 63136 KB Output is correct
13 Incorrect 645 ms 87348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 43000 KB Output is correct
2 Correct 41 ms 43176 KB Output is correct
3 Correct 39 ms 43152 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42580 KB Output is correct
6 Correct 41 ms 43228 KB Output is correct
7 Correct 38 ms 42704 KB Output is correct
8 Correct 40 ms 43100 KB Output is correct
9 Correct 41 ms 43384 KB Output is correct
10 Correct 38 ms 42716 KB Output is correct
11 Correct 192 ms 54516 KB Output is correct
12 Correct 400 ms 63136 KB Output is correct
13 Incorrect 645 ms 87348 KB Output isn't correct
14 Halted 0 ms 0 KB -