oj.uz

Submission #23613

# Submission time Handle Problem Language Result Execution time Memory
23613 2017-05-15T22:12:10 Z Hiasat Tropical Garden (IOI11_garden) C++14
49 / 100
 648 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 = -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;
			for(int it = 0 ; it < 10 ; 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 34 ms 43000 KB Output is correct
2 Correct 39 ms 43140 KB Output is correct
3 Correct 39 ms 43124 KB Output is correct
4 Correct 37 ms 42680 KB Output is correct
5 Correct 38 ms 42584 KB Output is correct
6 Correct 41 ms 43236 KB Output is correct
7 Correct 39 ms 42616 KB Output is correct
8 Correct 40 ms 43076 KB Output is correct
9 Correct 43 ms 43360 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 43000 KB Output is correct
2 Correct 39 ms 43140 KB Output is correct
3 Correct 39 ms 43124 KB Output is correct
4 Correct 37 ms 42680 KB Output is correct
5 Correct 38 ms 42584 KB Output is correct
6 Correct 41 ms 43236 KB Output is correct
7 Correct 39 ms 42616 KB Output is correct
8 Correct 40 ms 43076 KB Output is correct
9 Correct 43 ms 43360 KB Output is correct
10 Correct 39 ms 42612 KB Output is correct
11 Correct 219 ms 54580 KB Output is correct
12 Correct 397 ms 63132 KB Output is correct
13 Incorrect 648 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 34 ms 43000 KB Output is correct
2 Correct 39 ms 43140 KB Output is correct
3 Correct 39 ms 43124 KB Output is correct
4 Correct 37 ms 42680 KB Output is correct
5 Correct 38 ms 42584 KB Output is correct
6 Correct 41 ms 43236 KB Output is correct
7 Correct 39 ms 42616 KB Output is correct
8 Correct 40 ms 43076 KB Output is correct
9 Correct 43 ms 43360 KB Output is correct
10 Correct 39 ms 42612 KB Output is correct
11 Correct 219 ms 54580 KB Output is correct
12 Correct 397 ms 63132 KB Output is correct
13 Incorrect 648 ms 87348 KB Output isn't correct
14 Halted 0 ms 0 KB -