oj.uz

Submission #39245

# Submission time Handle Problem Language Result Execution time Memory
39245 2018-01-10T12:02:16 Z 14kg Tropical Garden (IOI11_garden) C++11
49 / 100
 609 ms 262148 KB 
#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001

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

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[]) {
	if (n >= 30) return;
	n = _n, start = _s + 1, p[0] = 1;
	for (int i = 1; i < 30; 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], 29), g(start, 1, Q[i], 29);
		answer(tot);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 218824 KB Output is correct
2 Correct 205 ms 219000 KB Output is correct
3 Correct 205 ms 218992 KB Output is correct
4 Correct 207 ms 218716 KB Output is correct
5 Correct 209 ms 218728 KB Output is correct
6 Correct 211 ms 218944 KB Output is correct
7 Correct 210 ms 218800 KB Output is correct
8 Correct 211 ms 218860 KB Output is correct
9 Correct 214 ms 218996 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 218824 KB Output is correct
2 Correct 205 ms 219000 KB Output is correct
3 Correct 205 ms 218992 KB Output is correct
4 Correct 207 ms 218716 KB Output is correct
5 Correct 209 ms 218728 KB Output is correct
6 Correct 211 ms 218944 KB Output is correct
7 Correct 210 ms 218800 KB Output is correct
8 Correct 211 ms 218860 KB Output is correct
9 Correct 214 ms 218996 KB Output is correct
10 Correct 205 ms 218804 KB Output is correct
11 Correct 228 ms 222136 KB Output is correct
12 Correct 250 ms 224576 KB Output is correct
13 Runtime error 609 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 218824 KB Output is correct
2 Correct 205 ms 219000 KB Output is correct
3 Correct 205 ms 218992 KB Output is correct
4 Correct 207 ms 218716 KB Output is correct
5 Correct 209 ms 218728 KB Output is correct
6 Correct 211 ms 218944 KB Output is correct
7 Correct 210 ms 218800 KB Output is correct
8 Correct 211 ms 218860 KB Output is correct
9 Correct 214 ms 218996 KB Output is correct
10 Correct 205 ms 218804 KB Output is correct
11 Correct 228 ms 222136 KB Output is correct
12 Correct 250 ms 224576 KB Output is correct
13 Runtime error 609 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -