Submission #1268566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268566		brendonw	세계 지도 (IOI25_worldmap)	C++20	0 / 100	6 ms	1096 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {

	vector<vector<int>> ans(3 * N, vector<int>(3 * N, 0));
	vector<vector<int>> adj(N);
	for (int i = 0; i < M; ++i) {
		adj[--A[i]].push_back(--B[i]);
		adj[B[i]].push_back(A[i]);
	}
	for (int i = 0; i < N; ++i) {
		sort(adj[i].begin(), adj[i].end());
		adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
	}
	vector<bool> visited(N, false);
	vector<int> tour;
	vector<vector<int>> backedge(N);
	auto dfs = [&](int u, auto &&self) -> void {
		visited[u] = true;
		tour.push_back(u);
		for (auto &v: adj[u]) {
			if (!visited[v]) {
				self(v, self);
				tour.push_back(u);
			} else {
				backedge[u].push_back(v);
			}
		}
	};
	dfs(0, dfs);
	for (int diag = 0; diag < 6 * N; ++diag) {
		int idx = 0;
		for (int i = max(0, diag - 3 * N + 1); i <= min(diag, 3 * N - 1); ++i) {
			int j = diag - i;
			if (diag % 3 == 1 && idx < backedge[tour[diag / 3]].size()) {
				ans[i][j] = backedge[tour[diag / 3]][idx++] + 1;
			} else {
				ans[i][j] = tour[diag / 3] + 1;
			}
		}
	}
	return ans;
}

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