Submission #1250385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250385		Temmie	World Map (IOI25_worldmap)	C++20	12 / 100	15 ms	1832 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;
	bool canskip = false;
};

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::cerr << "rt = " << rt << std::endl;
	// for (int i = 0; i < n; i++) {
	// 	std::cerr << i << ":";
	// 	for (int x : t[i]) std::cerr << " " << x;
	// 	std::cerr << std::endl;
	// }
	// assert(t[rt].size() == 1);
	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;
		bool leafnei = false;
		for (int x : t[node]) if (t[x].size() == 1) leafnei = true;
		if (g[node].size() == t[node].size() && !leafnei) {
			line.wide = false;
			line.who = node;
		} else {
			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, { }, true });
		}
	};
	if (g[rt].size() == 1) dfs(dfs, t[rt][0], rt);
	else dfs(dfs, rt, -1);
	std::vector <int> cnt(n, 0);
	for (const Line& line : lines) cnt[line.who]++;
	// std::cerr << lines.size() << " lines before pruning" << std::endl;
	while (!lines.back().wide && cnt[lines.back().who] > 1) cnt[lines.back().who]--, lines.pop_back();
	// std::cerr << lines.size() << " lines after pruning" << std::endl;
	// assert(lines.back().wide);
	{
		std::vector <std::pair <int, int>> sq;
		int l, r;
		for (l = 0, r = 0; r < (int) lines.size(); r++) {
			if (lines[r].wide || !lines[r].canskip) {
				if (l == r) {
					l++;
					continue;
				}
				sq.emplace_back(l, r - 1);
				l = r + 1;
			}
		}
		assert(r == (int) lines.size());
		if (l < r) sq.emplace_back(l, r - 1);
		std::vector <Line> nlines;
		for (int i = 0, j = 0; i < (int) lines.size(); i++) {
			if (lines[i].wide || !lines[i].canskip) {
				nlines.push_back(lines[i]);
				continue;
			}
			assert(j < (int) sq.size());
			assert(sq[j].first == i);
			int s = lines[sq[j].first].who;
			int e = lines[sq[j].second].who;
			if (s == e) {
				nlines.push_back(lines[i]);
				j++;
				continue;
			}
			std::vector <int> par(n, -1);
			std::queue <std::pair <int, int>> q;
			q.emplace(s, s);
			while (q.size()) {
				auto [v, p] = q.front();
				q.pop();
				if (par[v] != -1) continue;
				par[v] = p;
				for (int x : g[v]) q.emplace(x, v);
			}
			// std::cerr << s << " -> " << e << " par:";
			// for (int x : par) std::cerr << " " << x;
			// std::cerr << std::endl;
			std::vector <int> path;
			int v = e;
			do {
				path.push_back(v);
				v = par[v];
			} while (v != par[v]);
			assert(path.back() != s);
			path.push_back(s);
			while (path.size()) {
				Line line;
				line.wide = false;
				line.who = path.back();
				path.pop_back();
				nlines.push_back(line);
			}
			while (i < (int) lines.size() && lines[i].wide == false) i++;
			i--;
			j++;
		}
		lines = nlines;
	}
	const int SZ = n * 2;
	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) {
			first = false;
			i = std::min(i, SZ - 1);
			j = std::min(j, SZ - 1);
			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];
	// for (int I = 0; I < SZ; I++)
	// 	for (int J = 0; J < SZ; J++)
	// 		std::cerr << std::setw(2) << ans[I][J] << " \n"[J + 1 == SZ];
	// {
	// 	std::set <std::pair <int, int>> ed;
	// 	for (i = 0; i < m; i++) ed.insert({ a[i], b[i] }), ed.insert({ b[i], a[i] });
	// 	for (i = 0; i < n; i++) ed.insert({ i, i });
	// 	for (i = 0; i < SZ; i++) {
	// 		for (j = 0; j < SZ; j++) {
	// 			if (i + 1 < SZ) assert(ed.contains({ ans[i][j] - 1, ans[i + 1][j] - 1 }));
	// 			if (j + 1 < SZ) assert(ed.contains({ ans[i][j] - 1, ans[i][j + 1] - 1 }));
	// 		}
	// 	}
	// }
	return ans;
}

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