Submission #1083896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083896		EmmaXII	Tropical Garden (IOI11_garden)	C++17	0 / 100	1 ms	604 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 baby = goal;
		int giant = goal;
		int ans = 0;
		do {
			baby = succ[baby];
			giant = succ[succ[giant]];
			ans++;
		} while (baby != giant);
		return ans;
	};

	int clen = get_clen();

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

	bool in_cycle = check_in_cycle(goal);
	bool in_cycle2 = false;
	if (goal2 != -1) in_cycle2 = check_in_cycle(goal2);

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

	auto get_closest = [&](int fin, bool cycle) {
		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 sumfreq(E+1, 0);
	vi freq1 = get_closest(goal, in_cycle);
	for (int i=0;i<=E;i++) sumfreq[i] += freq1[i];

	if (goal2 != -1) {
		vi freq2 = get_closest(goal2, in_cycle2);
		for (int i=0;i<=E;i++) sumfreq[i] += freq2[i];
	}

	auto do_query = [&](int k) {
		if (k > E) {
			k %= clen;
			k += ((E - k)/clen) * clen;
		}
		return sumfreq[k];
	};

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