제출 #1268573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268573		brendonw	World Map (IOI25_worldmap)	C++20	100 / 100	19 ms	2888 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(2 * N, vector<int>(2 * 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<bool> done(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);
	int t = 0;
	for (int diag = 0; diag < 4 * N; ++diag) {
		if (t >= tour.size()) {
			for (int i = max(0, diag - 2 * N + 1); i <= min(diag, 2 * N - 1); ++i) {
				int j = diag - i;
				ans[i][j] = 1;
			}
		} else if (!done[tour[t]]) {
			for (int d = diag; d < diag + 3; ++d) {
				int idx = 0;
				for (int i = max(0, d - 2 * N + 1); i <= min(d, 2 * N - 1); ++i) {
					int j = d - i;
					if (d == diag + 1 && idx < backedge[tour[t]].size()) {
						ans[i][j] = backedge[tour[t]][idx++] + 1;
					} else {
						ans[i][j] = tour[t] + 1;
					}
				}
			}
			diag += 2;
			done[tour[t]] = true;
		} else {
			for (int i = max(0, diag - 2 * N + 1); i <= min(diag, 2 * N - 1); ++i) {
				int j = diag - i;
				ans[i][j] = tour[t] + 1;
			}
		}
		t++;
	}
	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