oj.uz

Submission #39260

# Submission time Handle Problem Language Result Execution time Memory
39260 2018-01-10T12:44:30 Z 14kg Tropical Garden (IOI11_garden) C++11
69 / 100
 5000 ms 241696 KB 
#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001
#define MP 23

using namespace std;
int n, m, start, p[MP + 1], R, Rw, tot;
bool check[N][2][MP + 1];
pair<int, int> r[N];
vector<int> r1[N], r2[N];
vector<pair<int, int> > d[N][2][MP + 1];

void Push_r(int x, int y) {
	if (!r[x].first) r[x].first = y;
	else if (!r[x].second) r[x].second = y;
}
void f(int x, int y, int s) {
	if (s == 0 || check[x][y][s]) return;

	f(x, y, s - 1), check[x][y][s] = true;
	for (auto i : d[x][y][s - 1]) {
		f(i.first, i.second, s - 1);
		for (auto j : d[i.first][i.second][s - 1])
			d[x][y][s].push_back(j);
	}
}
void g(int x, int y, int R, int Rw) {
	if (R == 0) {
		if (y == 0 || r[x].first == 0) tot++;
		return;
	}
	while (p[Rw] > R) Rw--;

	f(x, y, Rw);
	for (auto i : d[x][y][Rw]) g(i.first, i.second, R - p[Rw], Rw);
}
void count_routes(int _n, int _m, int _s, int _r[][2], int Q_len, int Q[]) {
	n = _n, start = _s + 1, p[0] = 1;
	for (int i = 1; i <= MP; i++) p[i] = p[i - 1] * 2;

	for (int i = 0; i < _m; i++) {
		int x = _r[i][0] + 1, y = _r[i][1] + 1;
		Push_r(x, y), Push_r(y, x);
	}
	for (int i = 1; i <= n; i++) {
		if (!r[i].second) r[i].second = r[i].first, r[i].first = 0;

		if (r[i].first) r1[r[i].first].push_back(i);
		r2[r[i].second].push_back(i);

		if (r[r[i].first].first == i || (r[r[i].first].first == 0 && r[r[i].first].second == i)) d[r[i].first][1][0].push_back({ i,0 });
		if (r[r[i].second].first == i || (r[r[i].second].first == 0 && r[r[i].second].second == i)) d[r[i].second][1][0].push_back({ i,1 });
	}

	for (int i = 1; i <= n; i++) {
		for (auto j : r1[i])
			if (j != r[i].first && (r[i].first || r[i].second != j)) d[i][0][0].push_back({ j,0 });
		for (auto j : r2[i])
			if (j != r[i].first && (r[i].first || r[i].second != j)) d[i][0][0].push_back({ j,1 });
	}

	for (int i = 0; i < Q_len; i++) {
		tot = 0, g(start, 0, Q[i], MP), g(start, 1, Q[i], MP);
		answer(tot);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 176544 KB Output is correct
2 Correct 164 ms 176708 KB Output is correct
3 Correct 163 ms 176708 KB Output is correct
4 Correct 167 ms 176520 KB Output is correct
5 Correct 167 ms 176508 KB Output is correct
6 Correct 168 ms 176644 KB Output is correct
7 Correct 165 ms 176448 KB Output is correct
8 Correct 165 ms 176604 KB Output is correct
9 Correct 169 ms 176784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 176544 KB Output is correct
2 Correct 164 ms 176708 KB Output is correct
3 Correct 163 ms 176708 KB Output is correct
4 Correct 167 ms 176520 KB Output is correct
5 Correct 167 ms 176508 KB Output is correct
6 Correct 168 ms 176644 KB Output is correct
7 Correct 165 ms 176448 KB Output is correct
8 Correct 165 ms 176604 KB Output is correct
9 Correct 169 ms 176784 KB Output is correct
10 Correct 164 ms 176528 KB Output is correct
11 Correct 186 ms 179648 KB Output is correct
12 Correct 203 ms 181676 KB Output is correct
13 Correct 742 ms 233636 KB Output is correct
14 Correct 438 ms 202800 KB Output is correct
15 Correct 1039 ms 240044 KB Output is correct
16 Correct 742 ms 228740 KB Output is correct
17 Correct 729 ms 219100 KB Output is correct
18 Correct 204 ms 181492 KB Output is correct
19 Correct 407 ms 202488 KB Output is correct
20 Correct 1031 ms 241696 KB Output is correct
21 Correct 751 ms 231004 KB Output is correct
22 Correct 579 ms 211056 KB Output is correct
23 Correct 331 ms 197776 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 176544 KB Output is correct
2 Correct 164 ms 176708 KB Output is correct
3 Correct 163 ms 176708 KB Output is correct
4 Correct 167 ms 176520 KB Output is correct
5 Correct 167 ms 176508 KB Output is correct
6 Correct 168 ms 176644 KB Output is correct
7 Correct 165 ms 176448 KB Output is correct
8 Correct 165 ms 176604 KB Output is correct
9 Correct 169 ms 176784 KB Output is correct
10 Correct 164 ms 176528 KB Output is correct
11 Correct 186 ms 179648 KB Output is correct
12 Correct 203 ms 181676 KB Output is correct
13 Correct 742 ms 233636 KB Output is correct
14 Correct 438 ms 202800 KB Output is correct
15 Correct 1039 ms 240044 KB Output is correct
16 Correct 742 ms 228740 KB Output is correct
17 Correct 729 ms 219100 KB Output is correct
18 Correct 204 ms 181492 KB Output is correct
19 Correct 407 ms 202488 KB Output is correct
20 Correct 1031 ms 241696 KB Output is correct
21 Correct 751 ms 231004 KB Output is correct
22 Correct 579 ms 211056 KB Output is correct
23 Correct 331 ms 197776 KB Output is correct
24 Correct 164 ms 176468 KB Output is correct
25 Correct 188 ms 179972 KB Output is correct
26 Correct 213 ms 182204 KB Output is correct
27 Correct 757 ms 234404 KB Output is correct
28 Execution timed out 5066 ms 204028 KB Time limit exceeded
29 Halted 0 ms 0 KB -