Submission #39300

#	Time	Username	Problem	Language	Result	Execution time	Memory
39300		14kg	Tropical Garden (IOI11_garden)	C++11	100 / 100	3007 ms	8596 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001
#define MP 23

using namespace std;
int n, m, start, cycle1_len, cycle2_len;
int Sx, Sy, d[N][2], d1[N][2], d2[N][2];
pair<int, int> r[N];

void Push_r(int x, int y) {
	if (!r[x].first) r[x].first = y;
	else if (!r[x].second) r[x].second = y;
}
int dfs(int x, int y, int len) {
	d[x][y] = len;
	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	if (d[nx][ny]) {
		if (d[nx][ny] == 1) return len;
		else return -1;
	}
	return dfs(nx, ny, len + 1);
}
int dfs_find1(int x, int y) {
	if (x == start && y == 0) return 0;
	if (d1[x][y] != 0) return d1[x][y];

	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	d1[x][y] = -1, d1[x][y] = dfs_find1(nx, ny);
	if (d1[x][y] >= 0) d1[x][y]++;

	return d1[x][y];
}
int dfs_find2(int x, int y) {
	if (x == start && y == 1) return 0;
	if (d2[x][y] != 0) return d2[x][y];

	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	d2[x][y] = -1, d2[x][y] = dfs_find2(nx, ny);
	if (d2[x][y] >= 0) d2[x][y]++;

	return d2[x][y];
}
void count_routes(int _n, int _m, int _s, int _r[][2], int Q_len, int Q[]) {
	n = _n, start = _s + 1;
	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);
	}

	cycle1_len = dfs(start, 0, 1);
	for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0;
	cycle2_len = dfs(start, 1, 1);
	for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0;
	
	for (int i = 1; i <= n; i++) {
		if (d1[i][0] == 0) dfs_find1(i, 0);
		if (d2[i][0] == 0) dfs_find2(i, 0);
		if (i == start) d1[i][0] = 0;
	}

	for (int i = 0; i < Q_len; i++) {
		int res = 0;
		if (Q[i] == 0) { answer(1); continue; }
		for (int j = 1; j <= n; j++) {
			if (d1[j][0] == Q[i] || d2[j][0] == Q[i]) res++;
			else if ((d1[j][0] > 0 || j == start) && cycle1_len > 0 && Q[i] >= d1[j][0] && (Q[i] - d1[j][0]) % cycle1_len == 0) res++;
			else if (d2[j][0] > 0 && cycle2_len > 0 && Q[i] >= d2[j][0] && (Q[i] - d2[j][0]) % cycle2_len == 0) res++;
		} answer(res);
	}
}

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