제출 #39236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39236		14kg	열대 식물원 (Tropical Garden) (IOI11_garden)	C++11	0 / 100	207 ms	219016 KiB

garden

#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;
	//printf("f: %d %d %d\n", x, y, s);

	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);
	//	printf(" %d %d %d > %d %d %d\n", x, y, s, i.first, i.second, s - 1);
		for (auto j : d[i.first][i.second][s - 1])
			d[x][y][s].push_back(j);// , printf(" push - %d %d %d / %d %d\n", x, y, s, j.first, j.second);
	}
}
void g(int x, int y, int R, int Rw) {
	// printf("IN : %d %d %d\n", x, y, R);
	if (R == 0) { 
		if(y==0 || r[x].first==0) tot++; //printf("%d %d\n", x, y); return; 
		return;
	}
	while (p[Rw] > R) Rw--;
	// printf(" Rw= %d\n", 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 < 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) d[i][0][0].push_back({ j,0 });
		for (auto j : r2[i])
			if (j != r[i].first) d[i][0][0].push_back({ j,1 });
	}
	//printf(" = %d %d\n", d[1][1][0].size(),d[2][1][0][0].second);

	for (int i = 0; i < Q_len; i++) {
		//printf("\n(%d)\n", i);
		tot = 0, g(start, 0, Q[i], 29), g(start, 1, Q[i], 29);
		answer(tot);
	}
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31