oj.uz

Submission #23612

# Submission time Handle Problem Language Result Execution time Memory
23612 2017-05-15T21:56:15 Z Hiasat Tropical Garden (IOI11_garden) C++14
49 / 100
 628 ms 87360 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 (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 40 ms 43076 KB Output is correct
2 Correct 40 ms 43064 KB Output is correct
3 Correct 41 ms 43124 KB Output is correct
4 Correct 39 ms 42656 KB Output is correct
5 Correct 40 ms 42588 KB Output is correct
6 Correct 40 ms 43128 KB Output is correct
7 Correct 39 ms 42744 KB Output is correct
8 Correct 42 ms 43100 KB Output is correct
9 Correct 44 ms 43328 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 43076 KB Output is correct
2 Correct 40 ms 43064 KB Output is correct
3 Correct 41 ms 43124 KB Output is correct
4 Correct 39 ms 42656 KB Output is correct
5 Correct 40 ms 42588 KB Output is correct
6 Correct 40 ms 43128 KB Output is correct
7 Correct 39 ms 42744 KB Output is correct
8 Correct 42 ms 43100 KB Output is correct
9 Correct 44 ms 43328 KB Output is correct
10 Correct 39 ms 42644 KB Output is correct
11 Correct 196 ms 54576 KB Output is correct
12 Correct 390 ms 63140 KB Output is correct
13 Incorrect 628 ms 87360 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 43076 KB Output is correct
2 Correct 40 ms 43064 KB Output is correct
3 Correct 41 ms 43124 KB Output is correct
4 Correct 39 ms 42656 KB Output is correct
5 Correct 40 ms 42588 KB Output is correct
6 Correct 40 ms 43128 KB Output is correct
7 Correct 39 ms 42744 KB Output is correct
8 Correct 42 ms 43100 KB Output is correct
9 Correct 44 ms 43328 KB Output is correct
10 Correct 39 ms 42644 KB Output is correct
11 Correct 196 ms 54576 KB Output is correct
12 Correct 390 ms 63140 KB Output is correct
13 Incorrect 628 ms 87360 KB Output isn't correct
14 Halted 0 ms 0 KB -