Submission #1249549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249549		Temmie	World Map (IOI25_worldmap)	C++20	72 / 100	82 ms	9780 KiB

worldmap

#include <bits/stdc++.h>

int rt;

std::vector <std::vector <int>> maxdia(const std::vector <std::vector <int>>& g) {
	auto dia = [] (const std::vector <std::vector <int>>& t, int r) -> int {
		std::vector <int> d(t.size());
		d.assign(t.size(), -1);
		std::queue <int> q;
		q.push(r);
		d[r] = 0;
		int mx = 0;
		while (q.size()) {
			int v = q.front();
			q.pop();
			for (int x : t[v]) {
				if (d[x] != -1) continue;
				mx = std::max(mx, d[x] = d[v] + 1);
				q.push(x);
			}
		}
		for (int j = 0; j < (int) t.size(); j++) if (d[j] == mx) r = j;
		return r;
	};
	std::vector <std::vector <int>> res;
	int bst = -1;
	for (int i = 0; i < (int) g.size(); i++) {
		std::vector <std::vector <int>> t(g.size());
		std::vector <bool> vis(g.size(), false);
		auto dfs = [&] (auto&& self, int node) -> void {
			vis[node] = true;
			for (int x : g[node]) {
				if (vis[x]) continue;
				t[node].push_back(x);
				t[x].push_back(node);
				self(self, x);
			}
		};
		dfs(dfs, i);
		int now = dia(t, i);
		if (now > bst) bst = now, res = t, rt = i;
	}
	return res;
}

struct Line {
	bool wide = false;
	int who = -1;
	std::vector <int> nei;
};

std::vector <std::vector <int>> create_map(int n, int m, std::vector <int> a, std::vector <int> b) {
	if (n == 1) return { { 1 } };
	std::vector <std::vector <int>> g(n);
	for (int i = 0; i < m; i++) {
		g[--a[i]].push_back(--b[i]);
		g[b[i]].push_back(a[i]);
	}
	auto t = maxdia(g);
	std::vector <Line> lines;
	std::vector <int> d(n, -1);
	{
		std::queue <int> q;
		q.push(0);
		while (q.size()) {
			int v = q.front();
			q.pop();
			for (int x : t[v]) if (d[x] == -1) d[x] = d[v] + 1, q.push(x);
		}
	}
	std::vector <bool> vis(n, false);
	auto dfs = [&] (auto&& self, int node, int par = -1) -> void {
		std::sort(t[node].begin(), t[node].end(), [&] (int u, int v) -> bool { return d[u] < d[v]; });
		vis[node] = true;
		Line line;
		line.wide = true;
		line.who = node;
		for (int x : g[node]) {
			if (vis[x]) continue;
			line.nei.push_back(x);
		}
		if (line.nei.empty()) line.wide = false;
		lines.push_back(line);
		for (int x : t[node]) {
			if (x == par) continue;
			if (t[x].size() == 1) continue;
			self(self, x, node);
			lines.push_back({ false, node });
		}
	};
	if (g[rt].size() == 1) dfs(dfs, t[rt][0], rt);
	else dfs(dfs, rt, -1);
	while (!lines.back().wide) lines.pop_back();
	const int SZ = n * 4;
	std::vector <std::vector <int>> con(241, std::vector <int> (241, -1));
	int i = SZ, j = SZ;
	int last = -1;
	bool first = true;
	for (Line line : lines) {
		last = line.who;
		if (!line.wide) {
			assert(i >= 0 && j >= 0);
			for (int k = 0; k <= i; k++) con[k][j] = line.who + 1;
			for (int k = 0; k <= j; k++) con[i][k] = line.who + 1;
			i--;
			j--;
			continue;
		}
		if (i > j) {
			for (int k = 0; k <= j; k++) con[i][k] = con[i - 1][k] = con[i - 2][k] = line.who + 1;
			for (int k = 0; k < i; k++) con[k][j] = line.who + 1;
			i--;
			int k = 0;
			for (int x : line.nei) {
				assert(k < j);
				con[i][k] = x + 1;
				k += 2;
			}
			j--;
			i -= 2;
			if (first) j++;
			first = false;
		} else {
			for (int k = 0; k <= i; k++) con[k][j] = con[k][j - 1] = con[k][j - 2] = line.who + 1;
			for (int k = 0; k < j; k++) con[i][k] = line.who + 1;
			j--;
			int k = 0;
			for (int x : line.nei) {
				assert(k < i);
				con[k][j] = x + 1;
				k += 2;
			}
			i--;
			j -= 2;
			if (first) i++;
			first = false;
		}
	}
	{
		std::queue <std::pair <int, int>> q;
		q.emplace(0, 0);
		while (q.size()) {
			auto [I, J] = q.front();
			q.pop();
			if (con[I][J] != -1) continue;
			con[I][J] = last + 1;
			q.emplace(I + 1, J);
			q.emplace(I, J + 1);
		}
	}
	std::vector <std::vector <int>> ans(SZ, std::vector <int> (SZ, -1));
	for (int I = 0; I < SZ; I++)
		for (int J = 0; J < SZ; J++)
			ans[I][J] = con[I][J];
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 28 / 56