oj.uz

Submission #24880

# Submission time Handle Problem Language Result Execution time Memory
24880 2017-06-16T18:41:25 Z Hiasat Tropical Garden (IOI11_garden) C++14
69 / 100
 220 ms 34124 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

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

int need[MX * 2][2];

void connect(int u , int v, int N) {
	if (adj[u][0] == v || adj[u][0] == v - N)
		u = u + N;
	g[u].push_back(v);
}
void dfs(int u , int cost, int it) {
	if (need[u][it] != -1)
		return;
	if (cost)
		need[u][it] = cost;
	for (int i = 0; i < g[u].size(); ++i) {
		dfs(g[u][i], cost + 1, it);
	}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	memset(need, -1, sizeof need);
	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();
		if (adj[i].size())
			connect(adj[i][0], i, N);
		if (adj[i].size()) {
			if (adj[i].size() == 2) {
				connect(adj[i][1], i + N, N);
			} else {
				connect(adj[i][0], i + N, N);
			}
		}
	}
	dfs(P, 0, 0);
	dfs(P + N, 0, 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++) {
				int rem = G[k];
				if(rem < need[i][it])
					continue;
				if(need[i][it] == -1)
					continue;
				rem -= need[i][it];

				if(rem == 0 || (need[P+it*N][it] != -1 && rem%need[P+it*N][it] == 0)){
					res++;
				}
			}
		}
		answer(res);
	}
}

Compilation message

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:24: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 18 ms 16920 KB Output is correct
2 Correct 18 ms 16904 KB Output is correct
3 Correct 18 ms 16888 KB Output is correct
4 Correct 18 ms 16760 KB Output is correct
5 Correct 17 ms 16772 KB Output is correct
6 Correct 18 ms 17016 KB Output is correct
7 Correct 17 ms 16760 KB Output is correct
8 Correct 18 ms 16888 KB Output is correct
9 Correct 21 ms 17040 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16920 KB Output is correct
2 Correct 18 ms 16904 KB Output is correct
3 Correct 18 ms 16888 KB Output is correct
4 Correct 18 ms 16760 KB Output is correct
5 Correct 17 ms 16772 KB Output is correct
6 Correct 18 ms 17016 KB Output is correct
7 Correct 17 ms 16760 KB Output is correct
8 Correct 18 ms 16888 KB Output is correct
9 Correct 21 ms 17040 KB Output is correct
10 Correct 17 ms 16732 KB Output is correct
11 Correct 30 ms 18856 KB Output is correct
12 Correct 53 ms 20168 KB Output is correct
13 Correct 76 ms 34124 KB Output is correct
14 Correct 171 ms 27576 KB Output is correct
15 Correct 219 ms 27968 KB Output is correct
16 Correct 169 ms 25548 KB Output is correct
17 Correct 146 ms 24532 KB Output is correct
18 Correct 51 ms 20408 KB Output is correct
19 Correct 175 ms 27776 KB Output is correct
20 Correct 220 ms 27988 KB Output is correct
21 Correct 178 ms 25084 KB Output is correct
22 Correct 155 ms 23936 KB Output is correct
23 Correct 182 ms 28256 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16920 KB Output is correct
2 Correct 18 ms 16904 KB Output is correct
3 Correct 18 ms 16888 KB Output is correct
4 Correct 18 ms 16760 KB Output is correct
5 Correct 17 ms 16772 KB Output is correct
6 Correct 18 ms 17016 KB Output is correct
7 Correct 17 ms 16760 KB Output is correct
8 Correct 18 ms 16888 KB Output is correct
9 Correct 21 ms 17040 KB Output is correct
10 Correct 17 ms 16732 KB Output is correct
11 Correct 30 ms 18856 KB Output is correct
12 Correct 53 ms 20168 KB Output is correct
13 Correct 76 ms 34124 KB Output is correct
14 Correct 171 ms 27576 KB Output is correct
15 Correct 219 ms 27968 KB Output is correct
16 Correct 169 ms 25548 KB Output is correct
17 Correct 146 ms 24532 KB Output is correct
18 Correct 51 ms 20408 KB Output is correct
19 Correct 175 ms 27776 KB Output is correct
20 Correct 220 ms 27988 KB Output is correct
21 Correct 178 ms 25084 KB Output is correct
22 Correct 155 ms 23936 KB Output is correct
23 Correct 182 ms 28256 KB Output is correct
24 Incorrect 19 ms 16732 KB Output isn't correct
25 Halted 0 ms 0 KB -