oj.uz

답안 #39259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39259 2018-01-10T12:43:58 Z 14kg 열대 식물원 (Tropical Garden) (IOI11_garden) C++11
49 / 100
 929 ms 262144 KB 
#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001
#define MP 26

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

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 197760 KB Output is correct
2 Correct 187 ms 197868 KB Output is correct
3 Correct 186 ms 197724 KB Output is correct
4 Correct 184 ms 197588 KB Output is correct
5 Correct 183 ms 197568 KB Output is correct
6 Correct 185 ms 197812 KB Output is correct
7 Correct 187 ms 197624 KB Output is correct
8 Correct 188 ms 197732 KB Output is correct
9 Correct 188 ms 197960 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 197760 KB Output is correct
2 Correct 187 ms 197868 KB Output is correct
3 Correct 186 ms 197724 KB Output is correct
4 Correct 184 ms 197588 KB Output is correct
5 Correct 183 ms 197568 KB Output is correct
6 Correct 185 ms 197812 KB Output is correct
7 Correct 187 ms 197624 KB Output is correct
8 Correct 188 ms 197732 KB Output is correct
9 Correct 188 ms 197960 KB Output is correct
10 Correct 184 ms 197640 KB Output is correct
11 Correct 201 ms 200924 KB Output is correct
12 Correct 224 ms 203056 KB Output is correct
13 Correct 766 ms 255572 KB Output is correct
14 Correct 466 ms 225996 KB Output is correct
15 Runtime error 929 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 197760 KB Output is correct
2 Correct 187 ms 197868 KB Output is correct
3 Correct 186 ms 197724 KB Output is correct
4 Correct 184 ms 197588 KB Output is correct
5 Correct 183 ms 197568 KB Output is correct
6 Correct 185 ms 197812 KB Output is correct
7 Correct 187 ms 197624 KB Output is correct
8 Correct 188 ms 197732 KB Output is correct
9 Correct 188 ms 197960 KB Output is correct
10 Correct 184 ms 197640 KB Output is correct
11 Correct 201 ms 200924 KB Output is correct
12 Correct 224 ms 203056 KB Output is correct
13 Correct 766 ms 255572 KB Output is correct
14 Correct 466 ms 225996 KB Output is correct
15 Runtime error 929 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -