Submission #1262958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262958		am_aadvik	World Map (IOI25_worldmap)	C++20	58 / 100	166 ms	23900 KiB

worldmap

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

vector<int> g[45];
int res[1000][1000] = { 0 }, n, st = 500;
vector<bool> vis(45), used(45);

vector<int> dfs(int node, int si, int sj, int ei, int ej) {
	if (si == -1) {
		for (int i = st; i <= (st + n + n); ++i)
			res[i][st] = node;
		si = sj = ej = st, ei = st + n + n;
	}
	else {
		for (int i = (si - 1); i <= (ei + 1); ++i)
			res[i][sj - 1] = res[i][ej + 1] = node;
		for (int j = (sj - 1); j <= (ej + 1); ++j)
			res[si - 1][j] = res[ei + 1][j] = node;
		if (!used[node]) {
			for (int i = (si - 1); i <= (ei + 1); ++i)
				res[i][ej + 3] = node;
			int ci = si;
			for (auto x : g[node])
				res[ci][ej + 2] = x, ci += 2;
			for (int i = si; i <= ei; ++i)
				if (!res[i][ej + 2])
					res[i][ej + 2] = node;
			res[si - 1][ej + 2] = res[ei + 1][ej + 2] = node;
			--si, ++ei, --sj, ej += 3, used[node] = 1;
		}
		else --si, ++ei, --sj, ++ej;
	}
	bool l = 1; vis[node] = 1;
	for (auto x : g[node])
		if (!vis[x]) {
			auto r = dfs(x, si, sj, ei, ej);
			si = r[0], sj = r[1], ei = r[2], ej = r[3];

			for (int i = (si - 1); i <= (ei + 1); ++i)
				res[i][sj - 1] = res[i][ej + 1] = node;
			for (int j = (sj - 1); j <= (ej + 1); ++j)
				res[si - 1][j] = res[ei + 1][j] = node;
			if (!used[node]) {
				for (int i = (si - 1); i <= (ei + 1); ++i)
					res[i][ej + 3] = node;
				int ci = si;
				for (auto x : g[node])
					res[ci][ej + 2] = x, ci += 2;
				for (int i = si; i <= ei; ++i)
					if (!res[i][ej + 2])
						res[i][ej + 2] = node;
				res[si - 1][ej + 2] = res[ei + 1][ej + 2] = node;
				--si, ++ei, --sj, ej += 3, used[node] = 1;
			}
			else --si, ++ei, --sj, ++ej;
			l = 0;
		}
	return { si, sj, ei, ej };
}

vector<vector<int>> create_map(int N, int m, vector<int> a, vector<int> b) {
	n = N;
	for (int i = 0; i < m; ++i)
		g[a[i]].push_back(b[i]),
		g[b[i]].push_back(a[i]);
	auto x = dfs(1, -1, -1, -1, -1);
	int mx = max(x[2] - x[0] + 1, x[3] - x[1] + 1);
	vector<vector<int>> ans(mx, vector<int>(mx, 1));
	int si = x[0], sj = x[1];
	for (int i = si; i <= x[2]; ++i)
		for (int j = sj; j <= x[3]; ++j)
			ans[i - si][j - sj] = res[i][j];
	for (int i = 0; i <= n; ++i)
		g[i].clear();
	memset(res, 0, sizeof(res));
	vis.assign(45, 0), used.assign(45, 0);
	return ans;
}
/*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 << "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 << "FAIL!"; return 0;
				}
		}
	cout << "Success!" << 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: 14 / 56