Submission #1084037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084037		EmmaXII	Tropical Garden (IOI11_garden)	C++17	100 / 100	338 ms	54968 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

#define all(x) x.begin(), x.end()

// void answer(int x) {
// 	cout << x << endl;
// }

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
	vvi adj(n);

	vector<pair<int, int>> edges;
	for (int i=0;i<m;i++) {
		int u = r[i][0];
		int v = r[i][1];
		adj[u].push_back(v);
		adj[v].push_back(u);

		edges.push_back({u, v});
		edges.push_back({v, u});
	}

	vi fmax(n, -1);
	vi smax(n, -1);
	for (int i=0;i<n;i++) {
		fmax[i] = adj[i][0];
		if (adj[i].size() > 1) smax[i] = adj[i][1];
	}

	int E = (int)edges.size();
	map<pair<int, int>, int> lookup;
	for (int i=0;i<E;i++) {
		lookup[edges[i]] = i;
	}
	vi succ(E, -1);
	for (int i=0;i<E;i++) {
		auto [u, v] = edges[i];
		if (smax[v] == -1 || fmax[v] != u) succ[i] = lookup[{v, fmax[v]}];
		else succ[i] = lookup[{v, smax[v]}];
	}

	int goal = lookup[{p, fmax[p]}];
	int goal2 = -1;
	if (smax[p] != -1) goal2 = lookup[{p, smax[p]}];
	
	// get cycle length
	auto get_clen = [&](int start) {
		int baby = start;
		int giant = start;
		int ans = 0;
		do {
			baby = succ[baby];
			giant = succ[succ[giant]];
			ans++;
		} while (baby != giant);
		return ans;
	};

	auto check_in_cycle = [&](int v, int clen) {
		int w = v;
		for (int i=0;i<clen;i++) w = succ[w];
		return w == v;
	};

	int clen1 = get_clen(goal);
	bool in_cycle1 = check_in_cycle(goal, clen1);

	int clen2 = 1;
	bool in_cycle2 = false;
	if (goal2 != -1){
		clen2 = get_clen(goal2);
		in_cycle2 = check_in_cycle(goal2, clen2);
	}

	vvi radj(E);
	for (int i=0;i<E;i++) radj[succ[i]].push_back(i);

	auto get_closest = [&](int fin, bool cycle, int clen) {
		vi dists(E, -1);
		dists[fin] = 0;

		queue<int> bfs;
		bfs.push(fin);
		while (!bfs.empty()) {
			int cur = bfs.front(); bfs.pop();

			for (int w : radj[cur]) {
				if (dists[w] != -1) continue;
				dists[w] = dists[cur] + 1;
				bfs.push(w);
			}
		}

		vi ans(E+1, 0);
		for (int i=0;i<n;i++) {
			int e = lookup[{i, fmax[i]}];
			int d = dists[e];
			if (d >= 0) ans[d]++;
		}

		if (cycle) {
			for (int i=clen;i<=E;i++) ans[i] += ans[i-clen];
		}

		return ans;
	};

	vi freq1 = get_closest(goal, in_cycle1, clen1);
	vi freq2;
	if (goal2 != -1) {
		freq2 = get_closest(goal2, in_cycle2, clen2);
	}

	auto sub_query = [&](int k, vi& freq, bool cycle, int clen) {
		if (k > E) {
			if (!cycle) return 0;
			k %= clen;
			k += ((E - k)/clen) * clen;
		}
		return freq[k];
	};

	auto do_query = [&](int k) {
		int ans = 0;
		ans += sub_query(k, freq1, in_cycle1, clen1);
		if (goal2 != -1) ans += sub_query(k, freq2, in_cycle2, clen2);
		return ans;
	};

	vi G(g, g+q);
	for (int k : G) {
		answer(do_query(k));
	}
}

// int main() {
// 	std::ios::sync_with_stdio(false);
// 	std::cin.tie(NULL);

// 	{
// 		int N = 6;
// 		int M = 6;
// 		int P = 0;
// 		int R[][2] = {
// 			{1, 2},
// 			{0, 1},
// 			{0, 3},
// 			{3, 4},
// 			{4, 5},
// 			{1, 5}
// 		};
// 		int Q = 1;
// 		int G[] = {3};
// 		count_routes(N, M, P, R, Q, G);
// 	}
// 	cout << "-----------" << endl;
// 	{
// 		int N = 5;
// 		int M = 5;
// 		int P = 2;
// 		int R[][2] = {
// 			{1, 0},
// 			{1, 2},
// 			{3, 2},
// 			{1, 3},
// 			{4, 2}
// 		};
// 		int Q = 2;
// 		int G[] = {3, 1};
// 		count_routes(N, M, P, R, Q, G);
// 	}

// 	return 0;
// }

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