Submission #1249381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249381		model_code	World Map (IOI25_worldmap)	C++20	100 / 100	24 ms	2932 KiB

worldmap

// sub6-2k.cpp
#include "worldmap.h"
#include <vector>
#include <iostream>
using namespace std;

std::vector<std::vector<int> > create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
	// step #1. preparation
	vector<vector<int> > G(N);
	for (int i = 0; i < M; i++) {
		A[i]--;
		B[i]--;
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	
	// step #2. make spanning tree
	vector<bool> vis(N, false);
	vector<int> depth(N);
	vector<int> tour, RA, RB;
	auto dfs = [&](auto& self, int x) -> void {
		vis[x] = true;
		tour.push_back(x);
		for (int i : G[x]) {
			if (!vis[i]) {
				depth[i] = depth[x] + 1;
				self(self, i);
				tour.push_back(x);
			} else if (depth[x] < depth[i]) {
				RA.push_back(x);
				RB.push_back(i);
			}
		}
	};
	dfs(dfs, 0);

	// step #3. construction
	vector<int> rank(N, -1), holder(N, -1);
	for (int i = 0; i < 2 * N - 1; i++) {
		int d = min(i, (2 * N - 2) - i);
		if (rank[tour[i]] < d) {
			rank[tour[i]] = d;
			holder[tour[i]] = i;
		}
	}
	vector<vector<int> > H(N);
	for (int i = 0; i < M - (N - 1); i++) {
		if (rank[RA[i]] < rank[RB[i]]) {
			swap(RA[i], RB[i]);
		}
		H[RA[i]].push_back(RB[i]);
	}
	vector<vector<int> > ans(2 * N, vector<int>(2 * N, 0));
	int cur = 0, parity = 0;
	for (int i = 0; i < 2 * N - 1; i++) {
		if (i == holder[tour[i]]) {
			int pos = 0;
			for (int j = 0; j < 2 * N; j++) {
				int ya = cur - j;
				if (0 <= ya && ya < 2 * N) {
					ans[j][ya] = tour[i];
				}
				int yb = (cur + 1) - j;
				if (0 <= yb && yb < 2 * N) {
					if (pos < int(H[tour[i]].size())) {
						ans[j][yb] = H[tour[i]][pos];
						pos++;
					} else {
						ans[j][yb] = tour[i];
					}
				}
				int yc = (cur + 2) - j;
				if (0 <= yc && yc < 2 * N) {
					ans[j][yc] = tour[i];
				}
			}
			cur += 3;
			parity ^= 1;
		} else {
			for (int j = 0; j < 2 * N; j++) {
				int ya = cur - j;
				if (0 <= ya && ya < 2 * N) {
					ans[j][ya] = tour[i];
				}
			}
			cur += 1;
		}
	}

	// step #4. final step
	for (int i = 0; i < int(ans.size()); i++) {
		for (int j = 0; j < int(ans.size()); j++) {
			ans[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: 56 / 56