Submission #1271318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271318		model_code	Telepathy (JOI25_telepathy)	C++20	100 / 100	70 ms	980 KiB

telepathy

// 5.99d turns solution for general cases

#include "telepathy.h"
#include <algorithm>
#include <iostream>

// make adjacency list
std::vector<std::vector<int> > make_graph(int N, const std::vector<int>& A, const std::vector<int>& B) {
	std::vector<std::vector<int> > G(N);
	for (int i = 0; i < N - 1; i++) {
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	return G;
}

// find centroid of tree
std::vector<int> find_centroid(int N, const std::vector<std::vector<int> >& G) {
	std::vector<int> res;
	std::vector<int> subsize(N, 1);
	auto dfs = [&](auto& self, int x, int pre) -> void {
		bool ok = true;
		for (int i : G[x]) {
			if (i != pre) {
				self(self, i, x);
				subsize[x] += subsize[i];
				if (subsize[i] * 2 > N) {
					ok = false;
				}
			}
		}
		if (ok && subsize[x] * 2 >= N) {
			res.push_back(x);
		}
	};
	dfs(dfs, 0, -1);
	return res;
}

// find S-T path on tree
std::vector<int> find_path(int N, std::vector<std::vector<int> > G, int S, int T) {
	std::vector<int> par(N, -1);
	auto dfs = [&](auto& self, int x, int pre) -> void {
		par[x] = pre;
		for (int i : G[x]) {
			if (i != pre) {
				self(self, i, x);
			}
		}
	};
	dfs(dfs, T, -1);
	std::vector<int> seq = {S};
	while (seq.back() != T) {
		seq.push_back(par[seq.back()]);
	}
	return seq;
}

// sequence of changes of (depth of A) - (depth of B)
std::vector<int> instruction(int N, int player) {
	double mul = 1.0;
	std::vector<int> seq;
	int turn = 0, l = 0, r = 0;
	while (int(seq.size()) < 10 * N) {
		if (turn == 0) {
			int nr = int(mul);
			int pre = l;
			for (int i = l + 1; i <= r; i++) {
				if ((i & 1) == 0) {
					seq.push_back(i - pre);
					pre = i;
				}
			}
			seq.push_back((r + 1) - pre);
			for (int i = r + 2; i <= nr; i++) {
				seq.push_back(+1);
			}
			r = nr;
		} else {
			int nl = -int(mul);
			int pre = r;
			for (int i = r - 1; i >= l; i--) {
				if ((i & 1) == 1) {
					seq.push_back(i - pre);
					pre = i;
				}
			}
			seq.push_back((l - 1) - pre);
			for (int i = l - 2; i >= nl; i--) {
				seq.push_back(-1);
			}
			l = nl;
		}
		turn ^= 1;
		mul *= 1.685;
	}
	seq.resize(10 * N);
	std::vector<int> res(10 * N);
	for (int i = 0; i < 10 * N; i++) {
		if (player == 0) {
			res[i] = (seq[i] >= +1 ? +1 : seq[i] == -2 ? -1 : 0);
		} else {
			res[i] = (seq[i] <= -1 ? +1 : seq[i] == +2 ? -1 : 0);
		}
	}
	return res;
}

// Aitana's strategy
std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S, int subtask) {
	std::vector<std::vector<int> > G = make_graph(N, A, B);
	std::vector<int> centroids = find_centroid(N, G);
	std::vector<int> path;
	for (int i : centroids) {
		std::vector<int> subpath = find_path(N, G, S, i);
		if (path.empty() || path.size() > subpath.size()) {
			path = subpath;
		}
	}
	std::vector<int> seq = instruction(N, 0);
	std::vector<int> res(10 * N + 1, -1);
	res[0] = S;
	int pos = 0;
	for (int i = 0; i < 10 * N; i++) {
		pos += seq[i];
		res[i + 1] = path[std::max(std::min(pos, int(path.size()) - 1), 0)];
	}
	return res;
}

// Bruno's strategy
std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D, int T, int subtask) {
	std::vector<std::vector<int> > G = make_graph(N, C, D);
	std::vector<int> centroids = find_centroid(N, G);
	std::vector<int> path;
	for (int i : centroids) {
		std::vector<int> subpath = find_path(N, G, T, i);
		if (path.empty() || path.size() > subpath.size()) {
			path = subpath;
		}
	}
	std::vector<int> seq = instruction(N, 1);
	std::vector<int> res(10 * N + 1, -1);
	res[0] = T;
	int pos = 0;
	for (int i = 0; i < 10 * N; i++) {
		pos += seq[i];
		res[i + 1] = path[std::max(std::min(pos, int(path.size()) - 1), 0)];
	}
	for (int i = 1; i <= 10 * N; i++) {
		if (centroids.size() == 2 && res[i - 1] == path.back() && (i == 10 * N || res[i + 1] == path.back())) {
			res[i] = centroids[0] + centroids[1] - path.back();
		}
	}
	return res;
}

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20