제출 #62371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62371		aome	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	49 / 100	30 ms	21752 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;

int T, st[N], ed[N], h[N], in[N];
int e[N], nxt[N], par[N], deg[N], pos[N];
vector<int> vec[N], cir[N], G[N];

int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }

void join(int u, int v) { par[find(u)] = find(v); }

void dfs(int u, int r) {
	st[u] = ++T, in[u] = r;
	for (auto v : G[u]) {
		if (deg[v]) continue;
		h[v] = h[u] + 1, dfs(v, r);
	}
	ed[u] = ++T;
}

void solve(int root) {
	if (vec[root].size() == 1) return;
	for (auto i : vec[root]) {
		deg[nxt[i]]++, G[nxt[i]].push_back(i);
	}
	queue<int> qu;
	for (auto i : vec[root]) if (!deg[i]) qu.push(i);
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		deg[nxt[u]]--;
		if (!deg[nxt[u]]) qu.push(nxt[u]);
	}
	for (auto i : vec[root]) {
		if (!deg[i]) continue;
		int cur = i;
		while (1) {
			pos[cur] = cir[root].size();
			cir[root].push_back(cur);
			cur = nxt[cur];
			if (cur == i) break;
		}
		break;
	}
	for (auto i : cir[root]) dfs(i, i);
}

void count_routes(int n, int m, int p, int R[][2], int q, int X[]) {
	if (n > 1000) return;
	for (int i = 0; i < n * 2; ++i) e[i] = nxt[i] = -1;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < 2; ++j) {
			int u = R[i][j];
			if (e[u] == -1) e[u] = i;
			else if (e[u + n] == -1) e[u + n] = i;
		}
	}
	for (int i = 0; i < n; ++i) {
		int j;
		j = R[e[i]][0] + R[e[i]][1] - i;
		if (e[j] == e[i]) {
			if (e[j + n] == -1) nxt[i] = j;
			else nxt[i] = j + n;
		}
		else nxt[i] = j;
		if (e[i + n] != -1) {
			j = R[e[i + n]][0] + R[e[i + n]][1] - i;
			if (e[j] == e[i + n]) {
				if (e[j + n] == -1) nxt[i + n] = j;
				else nxt[i + n] = j + n;
			}
			else nxt[i + n] = j;
		}
	}
	for (int i = 0; i < n * 2; ++i) par[i] = i;
	for (int i = 0; i < n * 2; ++i) if (nxt[i] != -1) join(i, nxt[i]);
	for (int i = 0; i < n * 2; ++i) vec[find(i)].push_back(i);
	for (int i = 0; i < n * 2; ++i) if (par[i] == i) solve(i);
	// for (int i = 0; i < n * 2; ++i) cout << nxt[i] << ' '; cout << '\n';
	for (int i = 0; i < q; ++i) {
		int res = 0;
		for (int j = 0; j < n; ++j) {
			// int cur = j, tmp = X[i];
			// while (tmp--) cur = nxt[cur];
			// if (cur == p || cur == p + n) res++;
			if (h[j] >= X[i]) {
				if (par[j] == par[p] && st[p] <= st[j] && ed[j] <= ed[p] && h[j] - h[p] == X[i]) ++res;
				else if (par[j] == par[p + n] && st[p + n] <= st[j] && ed[j] <= ed[p + n] && h[j] - h[p + n] == X[i]) ++res;
			}
			else {
				int tmp = cir[par[j]][(pos[in[j]] + X[i] - h[j]) % cir[par[j]].size()];
				if (tmp == p || tmp == p + n) res++;
			}
		}
		answer(res);
	}
}

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