oj.uz

답안 #39246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39246 2018-01-10T12:03:16 Z 14kg 열대 식물원 (Tropical Garden) (IOI11_garden) C++11
0 / 100
 205 ms 218780 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
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 205 ms 218780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 205 ms 218780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 205 ms 218780 KB Output isn't correct
2 Halted 0 ms 0 KB -