제출 #1248947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248947		eysbutno	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	0 / 100	1 ms	320 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using ll = long long;

constexpr int INF = 1e9;

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
	std::vector<std::vector<std::array<int, 2>>> adj(n), rev(n);
	for (int i = 0; i < m; i++) {
		adj[r[i][0]].push_back({r[i][1], i});
		adj[r[i][1]].push_back({r[i][0], i});
	}

	for (int i = 0; i < n; i++) {
		if (adj[i].size() > 2) adj[i].resize(2);
		for (const auto &[j, w] : adj[i]) {
			rev[j].push_back({i, w});
		}
	}

	std::vector<std::array<int, 2>> dist(n, {INF, INF});
	std::vector<std::array<int, 2>> to_p(n, {INF, INF});
	for (int tt = 0; tt < 2; tt++) {
		// t = 0 means we take best edge from p
		// t = 1 means we don't take best edge 
		if (tt == 1 && adj[p].size() == 1) break;

		std::queue<std::array<int, 3>> bfs;
		bfs.push({0, p, tt});
		while (!bfs.empty()) {
			const auto [t, u, f] = bfs.front();
			bfs.pop();
			if (dist[u][f] != INF) continue;
			dist[u][f] = t;

			int wt = adj[u][0][1];
			for (const auto &[j, w] : rev[u]) {
				if (f == 0 && w == wt && adj[u].size() > 1) continue;
				if (f == 1 && w != wt && adj[u].size() > 1) continue;
				int flag = w != adj[j][0][1];
				bfs.push({t + 1, j, flag});
			}
		}

		for (int i = 0; i < n; i++) {
			to_p[i][tt] = dist[i][0];
		}

		dist.assign(n, {INF, INF});
	}

	int cycle_len = 0, saw = 0;
	std::vector<std::array<bool, 2>> vis(n);

	int node = p, flag = 0, trav = 0;
	while (!vis[node][flag]) {
		vis[node][flag] = true;
		if (node == p && flag == 1) saw = trav;

		const auto [nxt, wt] = adj[node][flag];
		if (adj[nxt].size() == 1) {
			node = nxt, flag = 0;
		} else {
			node = nxt, flag = (adj[nxt][0][1] == wt);
		}

		trav++;
	}

	if (node == p) cycle_len = trav;
	else cycle_len = INT_MAX, saw = 0;

	for (int t = 0; t < q; t++) {
		int k = g[t], res = 0;
		for (int i = 0; i < n; i++) {
			if ((k - to_p[i][0]) % cycle_len == 0 || (k - to_p[i][1]) % cycle_len == saw) {
				res++;
			} else if ((k - to_p[i][1]) % cycle_len == 0 || (k - to_p[i][1]) % cycle_len == (cycle_len - saw)) {
				res++;
			}
		}

		answer(res);
	}
}

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