oj.uz

답안 #39245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -