# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1250922 | David_M | World Map (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#include "worldmap.h"
using namespace std;
vector<int> v[50];
int n, k;
int f[50];
void dfs(int x, int pa, vector<vector<int>> &ans) {
f[x] = 1;
for (int i = 0; i <= k; ++i) {
ans[i][k - i] = x;
}
k++;
for (int y : v[x]) {
if(f[y]) continue;
dfs(y, x, ans);
}
int e = max(0, k - 2 * n + 1);
if(x != 0) {
for (int y : v[x]) {
if(f[y] == 2) continue;
assert(f[y] == 1);
ans[e][k - e] = y;
e++;
}
k++;
while (e <= min(k, 2 * N - 1)) {
ans[e][k - e] = x;
e++;
}
k++;
}
for (int i = 0; i <= k; ++i) {
ans[i][k - 1] = pa;
}
k++;
f[x] = 2;
}
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, 1));
n = N;
for (int i = 0; i < 50; ++i) {
v[i].clear();
f[i] = 0;
}
for (int i = 0; i < M; ++i) {
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
dfs(0, 0, ans);
// assert(k == 4 * N - 2);
while (k <= 4 * N - 2) {
for (int i = max(0, k - 2 * N + 1); i <= min(k, 2 * N - 1); ++i) {
ans[i][j] = 0;
}
k++;
}
return ans;
}