Submission #1263402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263402		am_aadvik	World Map (IOI25_worldmap)	C++20	100 / 100	20 ms	2888 KiB

worldmap

#include <iostream>
#include <vector>
#include <cstring>
#include <map>
using namespace std;

vector<int> g[45], t[45], bck[45];
vector<bool> vis(45);
vector<pair<int, bool>> ord;
vector<int> dep(45), sub(45);
int dfs1(int node, int par) {
	vis[node] = sub[node] = 1;
	dep[node] = dep[par] + 1;
	for (auto x : g[node])
		if (!vis[x])
			t[node].push_back(x),
			t[x].push_back(node),
			sub[node] += dfs1(x, node);
	return sub[node];
}
void dfs2(int node, int par, bool b) {
	ord.push_back({ node, 1 });
	int mx = 0, id = 0;
	for (auto x : t[node])
		if (((x != par) && (sub[x] > mx)))
			mx = max(mx, sub[x]), id = x;
	for (auto x : t[node])
		if(x != par)
			if ((x != id) || (!b))
				dfs2(x, node, 0), ord.push_back({ node, 0 });
	if (id && b) dfs2(id, node, 1);
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
	if (n == 1) return { {1} };
	for (int i = 0; i < m; ++i)
		g[a[i]].push_back(b[i]),
		g[b[i]].push_back(a[i]);
	dfs1(1, 0);
	for (int i = 0; i < m; ++i) {
		int u = a[i], v = b[i];
		if (dep[u] > dep[v]) swap(u, v);
		bck[v].push_back(u);
	}
	dfs2(1, 0, 1);
	vector<vector<int>> res(2 * n, vector<int>(2 * n, 0));
	int dg = 0;
	for (auto x : ord) {
		int node = x.first;
		bool nbr = x.second;
		int i, j;
		if (dg < (2 * n))
			i = dg, j = 0;
		else
			i = 2 * n - 1, j = dg - 2 * n + 1;
		while (i >= 0 && (j < (2 * n)))
			res[i][j] = node, --i, ++j;
		++dg;
		if (dg < (2 * n))
			i = dg, j = 0;
		else
			i = 2 * n - 1, j = dg - 2 * n + 1;
		if (nbr && (bck[node].size())) {
			for (auto nb : bck[node])
				res[i][j] = nb, --i, ++j;
			if (dg < (2 * n))
				i = dg, j = 0;
			else
				i = 2 * n - 1, j = dg - 2 * n + 1;
			while (i >= 0 && (j < (2 * n))) {
				if (!res[i][j])
					res[i][j] = node;
				--i, ++j;
			}
			++dg;
			if (dg < (2 * n))
				i = dg, j = 0;
			else
				i = 2 * n - 1, j = dg - 2 * n + 1;
			while (i >= 0 && (j < (2 * n)))
				res[i][j] = node, --i, ++j;
			++dg;
		}
	}
	for (int i = 1; i < (2 * n); ++i)
		for (int j = 1; j < (2 * n); ++j)
			if (res[i][j] == 0)
				res[i][j] = res[i - 1][j];
	ord.clear();
	vis.assign(45, 0);
	dep.assign(45, 0);
	sub.assign(45, 0);
	for (int i = 0; i <= n; ++i)
		g[i].clear(), t[i].clear(), bck[i].clear();
	return res;
}
/*int main() {
	int n, m; cin >> n >> m;
	vector<int> a(m), b(m);
	map<pair<int, int>, bool> mp;
	for (int i = 1; i <= n; ++i) mp[{i, i}] = 1;
	for (int i = 0; i < m; mp[{a[i], b[i]}] = 1, ++i)
		cin >> a[i] >> b[i];
	auto res = create_map(n, m, a, b);
	cout << res.size() << endl;
	for (auto x : res) {
		for (auto y : x)
			cout << y << " ";
		cout << endl;
	}
	for (int i = 0; i < res.size(); ++i)
		for (int j = 0; j < res.size(); ++j) {
			if (i < (res.size() - 1))
				if (!mp[{res[i + 1][j], res[i][j]}] && !mp[{res[i][j], res[i + 1][j]}])
				{
					cout << res[i][j] << " " << res[i + 1][j] << endl;
					cout << "FAIL!"; return 0;
				}
			if (j < (res.size() - 1))
				if (!mp[{res[i][j + 1], res[i][j]}] && !mp[{res[i][j], res[i][j + 1]}])
				{
					cout << res[i][j] << " " << res[i + 1][j] << endl;
					cout << "FAIL!"; return 0;
				}
		}
	for (int i = 0; i < m; ++i) {
		bool ok = 0;
		for(int j = 0; j < res.size(); ++j)
			for(int k = 0; k < res.size(); ++k)
				if (res[j][k] == a[i]) {
					int dj[] = { 0, 0, +1, -1 };
					int dk[] = { 1, -1, 0, 0 };
					for (int d = 0; d < 4; ++d) {
						int nj = dj[d] + j, nk = dk[d] + k;
						if ((nj >= 0) && (nk >= 0) && (nk < res.size()) && (nj < res.size()))
							if (res[nj][nk] == b[i]) ok = 1;
					}
				}
		if(!ok) {
			cout << "FAIL!"; return 0;
		}
	}
	cout << "Success!" << endl;
	cout << "R = " << (float)res.size() / (float)n << endl;
}*/

• 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: 56 / 56