oj.uz

Submission #24887

# Submission time Handle Problem Language Result Execution time Memory
24887 2017-06-16T21:16:55 Z Hiasat Tropical Garden (IOI11_garden) C++14
100 / 100
 3549 ms 47016 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MX = 200011;
vector<int> adj[MX * 2], g[MX * 2];

int F[MX * 2][2], c[2];

void connect(int u , int v, int N) {
	if (adj[u][0] == v || adj[u][0] == v - N)
		u = u + N;
	//cout << "CONNECT " << u << " " << v << endl;
	g[u].push_back(v);
}
void dfs(int u , int p, int it) {
	for (int i = 0; i < g[u].size(); ++i) {
		int v = g[u][i];
		if (v == p) {
			c[it] = F[u][it] + 1;
		} else if (F[v][it] == -1) {
			F[v][it] = F[u][it] + 1;
			dfs(g[u][i], p, it);
		}
	}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	memset(F, -1, sizeof F);
	for (int i = 0; i < M; ++i) {
		adj[R[i][0]].push_back(R[i][1]);
		adj[R[i][1]].push_back(R[i][0]);
	}
	for (int i = 0; i < N; ++i) {
		while (adj[i].size() > 2)
			adj[i].pop_back();
		connect(adj[i][0], i, N);
		if (adj[i].size() == 2) {
			connect(adj[i][1], i + N, N);
		} else {
			connect(adj[i][0], i + N, N);
		}
	}
	F[P][0] = 0;
	dfs(P, P, 0);
	F[P+N][1] = 0;
	dfs(P + N, P+N, 1);
	/*	for (int i = 0; i < N; ++i){
			printf("%d = %d %d\n",i,need[i][0],need[i][1] );
		}*/
	for (int k = 0 ; k < Q ; k++) {
		int res = 0;
		for (int i = 0; i < N; ++i) {
			for (int it = 0 ; it < 2 ; it++) {
				if (F[i][it] == -1)
					continue;
				int rem = G[k];
				if (rem < F[i][it])
					continue;
				rem -= F[i][it];
				if (rem == 0 || (c[it] && rem %c[it] == 0)) {
					res++;
					break;
				}
			}
		}
		answer(res);
	}
}

Compilation message

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22428 KB Output is correct
2 Correct 23 ms 22408 KB Output is correct
3 Correct 23 ms 22392 KB Output is correct
4 Correct 23 ms 22248 KB Output is correct
5 Correct 22 ms 22196 KB Output is correct
6 Correct 23 ms 22436 KB Output is correct
7 Correct 22 ms 22236 KB Output is correct
8 Correct 22 ms 22336 KB Output is correct
9 Correct 25 ms 22620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22428 KB Output is correct
2 Correct 23 ms 22408 KB Output is correct
3 Correct 23 ms 22392 KB Output is correct
4 Correct 23 ms 22248 KB Output is correct
5 Correct 22 ms 22196 KB Output is correct
6 Correct 23 ms 22436 KB Output is correct
7 Correct 22 ms 22236 KB Output is correct
8 Correct 22 ms 22336 KB Output is correct
9 Correct 25 ms 22620 KB Output is correct
10 Correct 22 ms 22324 KB Output is correct
11 Correct 36 ms 24432 KB Output is correct
12 Correct 57 ms 25604 KB Output is correct
13 Correct 82 ms 41824 KB Output is correct
14 Correct 186 ms 32396 KB Output is correct
15 Correct 210 ms 32584 KB Output is correct
16 Correct 172 ms 30200 KB Output is correct
17 Correct 156 ms 29300 KB Output is correct
18 Correct 65 ms 25580 KB Output is correct
19 Correct 186 ms 32616 KB Output is correct
20 Correct 221 ms 32944 KB Output is correct
21 Correct 177 ms 30472 KB Output is correct
22 Correct 171 ms 30044 KB Output is correct
23 Correct 187 ms 34296 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22428 KB Output is correct
2 Correct 23 ms 22408 KB Output is correct
3 Correct 23 ms 22392 KB Output is correct
4 Correct 23 ms 22248 KB Output is correct
5 Correct 22 ms 22196 KB Output is correct
6 Correct 23 ms 22436 KB Output is correct
7 Correct 22 ms 22236 KB Output is correct
8 Correct 22 ms 22336 KB Output is correct
9 Correct 25 ms 22620 KB Output is correct
10 Correct 22 ms 22324 KB Output is correct
11 Correct 36 ms 24432 KB Output is correct
12 Correct 57 ms 25604 KB Output is correct
13 Correct 82 ms 41824 KB Output is correct
14 Correct 186 ms 32396 KB Output is correct
15 Correct 210 ms 32584 KB Output is correct
16 Correct 172 ms 30200 KB Output is correct
17 Correct 156 ms 29300 KB Output is correct
18 Correct 65 ms 25580 KB Output is correct
19 Correct 186 ms 32616 KB Output is correct
20 Correct 221 ms 32944 KB Output is correct
21 Correct 177 ms 30472 KB Output is correct
22 Correct 171 ms 30044 KB Output is correct
23 Correct 187 ms 34296 KB Output is correct
24 Correct 24 ms 22316 KB Output is correct
25 Correct 181 ms 24460 KB Output is correct
26 Correct 244 ms 25940 KB Output is correct
27 Correct 2133 ms 42632 KB Output is correct
28 Correct 1938 ms 34036 KB Output is correct
29 Correct 2535 ms 34340 KB Output is correct
30 Correct 1444 ms 31620 KB Output is correct
31 Correct 1516 ms 30608 KB Output is correct
32 Correct 286 ms 25952 KB Output is correct
33 Correct 1934 ms 34036 KB Output is correct
34 Correct 2419 ms 34316 KB Output is correct
35 Correct 1421 ms 31488 KB Output is correct
36 Correct 2251 ms 30604 KB Output is correct
37 Correct 1472 ms 35156 KB Output is correct
38 Correct 3549 ms 47016 KB Output is correct