| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1253358 | vuviet | 세계 지도 (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vector<vi> create_map(int n, int m, vi a, vi b) {
vector<vi> adj(n + 1);
for (int i = 0; i < m; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
// Step 1: Build DFS tree
vi parent(n + 1, 0), depth(n + 1, 0);
vector<vi> child(n + 1);
function<void(int)> dfs = [&](int u) {
for (int v : adj[u]) {
if (v == parent[u]) continue;
if (parent[v]) continue;
parent[v] = u;
depth[v] = depth[u] + 1;
child[u].push_back(v);
dfs(v);
}
};
parent[1] = -1;
dfs(1);
// Step 2: Euler tour
vi dfs_ord;
function<void(int)> dfs_euler = [&](int u) {
dfs_ord.push_back(u);
for (int v : child[u]) {
dfs_euler(v);
dfs_ord.push_back(u);
}
};
dfs_euler(1); // size = 2n - 1
// Step 3: Tin/tout for ancestor check
int timer = 0;
vi tin(n + 1), tout(n + 1);
function<void(int)> dfs_time = [&](int u) {
tin[u] = ++timer;
for (int v : child[u]) dfs_time(v);
tout[u] = timer;
};
dfs_time(1);
// Step 4: Build "need" array for back edges
vector<vi> need(n + 1);
for (int i = 0; i < m; i++) {
int u = a[i], v = b[i];
if (parent[v] == u || parent[u] == v) continue;
if (tin[v] < tin[u] && tout[v] > tout[u]) swap(u, v);
need[v].push_back(u);
}
// Step 5: Build rows for diagonals
vector<vi> rows;
vector<bool> seen(n + 1);
for (int u : dfs_ord) {
rows.push_back({u});
if (!seen[u] && !need[u].empty()) {
rows.push_back(need[u]);
rows.push_back({u});
seen[u] = true;
}
}
while ((int)rows.size() < 4 * n - 1)
rows.push_back(rows.back());
// Step 6: Fill grid along diagonals x + y = i
int K = 4 * n;
vector<vi> grid(K, vi(K, 0));
for (int i = 0; i < 4 * n - 1; i++) {
int len = min(i + 1, 4 * n - 1 - i);
while ((int)rows[i].size() < len)
rows[i].push_back(rows[i].back());
int p = 0;
for (int x = 0; x < K; x++) {
int y = i - x;
if (0 <= y && y < K && p < len)
grid[x][y] = rows[i][p++];
}
}
// Step 7: Fill any remaining 0s with color 1 (safe)
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++)
if (grid[i][j] == 0) grid[i][j] = 1;
// Optional: validate (assert all 3 conditions)
set<pair<int,int>> allowed;
for (int i = 0; i < m; i++) {
allowed.insert({a[i], b[i]});
allowed.insert({b[i], a[i]});
}
for (int i = 1; i <= n; i++) allowed.insert({i, i});
// 1. Every country must appear
vector<bool> appears(n + 1, false);
for (int r = 0; r < K; r++)
for (int c = 0; c < K; c++)
appears[grid[r][c]] = true;
for (int i = 1; i <= n; i++)
assert(appears[i]);
// 2. Every (a[i], b[i]) must appear as neighbors
set<pair<int,int>> seen;
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
int u = grid[r][c];
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
int v = grid[nr][nc];
if (u != v) seen.insert({u, v});
}
}
}
for (int i = 0; i < m; i++) {
assert(seen.count({a[i], b[i]}) || seen.count({b[i], a[i]}));
}
// 3. No invalid neighbor pairs
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
int u = grid[r][c];
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
int v = grid[nr][nc];
if (u != v) {
assert(allowed.count({u, v}));
}
}
}
}
return grid;
}