# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1262926 | am_aadvik | World Map (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
using namespace std;
vector<int> g[45];
int res[1000][1000] = { 0 }, n, st = 500;
vector<bool> vis(45), used(45);
vector<int> dfs(int node, int si, int sj, int ei, int ej) {
bool l = 1; vis[node] = 1;
for (auto x : g[node])
if (!vis[x]) {
auto r = dfs(x, si, sj, ei, ej);
si = r[0], sj = r[1], ei = r[2], ej = r[3];
for (int i = (si - 1); i <= (ei + 1); ++i)
res[i][sj - 1] = res[i][ej + 1] = node;
for (int j = (sj - 1); j <= (ej + 1); ++j)
res[si - 1][j] = res[ei + 1][j] = node;
for (int i = (si - 1); i <= (ei + 1); ++i)
res[i][ej + 3] = node;
if (!used[node]) {
int ci = si;
for (auto x : g[node])
res[ci][ej + 2] = x, ci += 2;
for (int i = si; i <= ei; ++i)
if (!res[i][ej + 2])
res[i][ej + 2] = node;
res[si - 1][ej + 2] = res[ei + 1][ej + 2] = node;
--si, ++ei, --sj, ej += 3, used[node] = 1;
}
l = 0;
}
if (l == true) {
if (si == -1) {
for (int i = st; i <= (st + n + n); ++i)
res[i][st] = node;
si = sj = ej = st, ei = st + n + n;
}
else {
for (int i = (si - 1); i <= (ei + 1); ++i)
res[i][sj - 1] = res[i][ej + 1] = node;
for (int j = (sj - 1); j <= (ej + 1); ++j)
res[si - 1][j] = res[ei + 1][j] = node;
for (int i = (si - 1); i <= (ei + 1); ++i)
res[i][ej + 3] = node;
int ci = si;
for (auto x : g[node])
res[ci][ej + 2] = x, ci += 2;
for (int i = si; i <= ei; ++i)
if (!res[i][ej + 2])
res[i][ej + 2] = node;
--si, ++ei, --sj, ej += 3, used[node] = 1;
}
}
return { si, sj, ei, ej };
}
vector<vector<int>> create_map(int N, int m, vector<int> a, vector<int> b) {
n = N;
for (int i = 0; i < m; ++i)
g[a[i]].push_back(b[i]),
g[b[i]].push_back(a[i]);
auto x = dfs(1, -1, -1, -1, -1);
int mx = max(x[2] - x[0] + 1, x[3] - x[1] + 1);
vector<vector<int>> ans(mx, vector<int>(mx, 1));
int si = x[0], sj = x[1];
for (int i = si; i <= x[2]; ++i)
for (int j = sj; j <= x[3]; ++j)
ans[i - si][j - sj] = res[i][j];
for (int i = 0; i <= n; ++i)
g[i].clear();
memset(res, 0, sizeof(res));
vis.assign(45, 0), used.assign(45, 0);
return ans;
}
/*int main() {
auto res = create_map(3, 2, { 1, 2 }, {2, 3});
cout << res.size() << endl;
for (auto x : res) {
for (auto y : x)
cout << y << " ";
cout << endl;
}
}*/