Submission #39244

#	Time	Username	Problem	Language	Result	Execution time	Memory
39244		14kg	Tropical Garden (IOI11_garden)	C++11	49 / 100	481 ms	262148 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<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]) {
		int tx = i, ty = 0;
		if (tx > n) tx -= n, ty++;
		if (!check[tx][ty][s - 1]) f(tx, ty, s - 1);
		for (auto j : d[tx][ty][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);
	int tx, ty;
	for (auto i : d[x][y][Rw]) {
		tx = i, ty = 0;
		if (tx > n) tx -= n, ty++;
		g(tx, ty, 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);
		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+n);
	}

	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);
		for (auto j : r2[i])
			if (j != r[i].first && (r[i].first || r[i].second!=j)) d[i][0][0].push_back(j+n);
	}

	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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31