#include <iostream>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
vector<int> g[45];
int res[1000][1000] = { 0 }, n, st = 0;
vector<bool> vis(45), used(45);
vector<int> dfs(int node, int si, int sj, int ei, int ej) {
if (si == -1) {
for (int i = st; i <= (st + n + n); i += 2)
res[i][st] = node;
si = st, ei = st + n + n, ej = sj = st;
used[node] = 1;
}
else {
int sic = (res[si][ej] == 0 ? si : si + 1);
int sip = (res[si][ej] == 0 ? si + 1 : si);
for (int i = sic; i <= ei; i += 2)
res[i][ej] = node;
for (int i = sip; i <= ei; i += 2)
res[i][ej + 1] = node;
if (!used[node]) {
int y = sic;
for (auto x : g[node])
res[y][ej + 1] = x, y += 2;
for (int i = si; i <= ei; ++i)
if (!res[i][ej + 1])
res[i][ej + 1] = node;
for (int i = sic; i <= ei; i += 2)
res[i][ej + 2] = node;
used[node] = 1, ej += 2;
}
else ++ej;
}
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];
if (si == -1) {
for (int i = st; i <= (st + n + n + 5); i += 2)
res[i][st] = node;
si = st, ei = st + n + n + 5, ej = sj = st;
used[node] = 1;
}
else {
int sic = (res[si][ej] == 0 ? si : si + 1);
int sip = (res[si][ej] == 0 ? si + 1 : si);
for (int i = sic; i <= ei; i += 2)
res[i][ej] = node;
for (int i = sip; i <= ei; i += 2)
res[i][ej + 1] = node;
if (!used[node]) {
int y = sic;
for (auto x : g[node])
res[y][ej + 1] = x, y += 2;
for (int i = si; i <= ei; ++i)
if (!res[i][ej + 1])
res[i][ej + 1] = node;
for (int i = sic; i <= ei; i += 2)
res[i][ej + 2] = node;
used[node] = 1, ej += 2;
}
else ++ej;
}
}
return { si, sj, ei, ej };
}
vector<vector<int>> create_map(int N, int m, vector<int> a, vector<int> b) {
n = N;
if (n == 1) return{ {1} };
if (n == 2) return { {1, 2}, {1, 2} };
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);
vector<vector<int>> ans(x[2] - x[0] + 1, vector<int>(x[3] - x[1] + 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 (auto &x : ans) for (auto &y : x) y = max(1, y);
while (ans.size() < ans[0].size())
ans.push_back(ans[0]);
while (ans.size() > ans[0].size())
for (int i = 0; i < ans.size(); ++i)
ans[i].push_back(ans[i].back());
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() {
int n, m; cin >> n >> m;
vector<int> a(m), b(m);
map<pair<int, int>, bool> mp;
for (int i = 1; i <= n; ++i) mp[{i, i}] = 1;
for (int i = 0; i < m; mp[{a[i], b[i]}] = 1, ++i)
cin >> a[i] >> b[i];
auto res = create_map(n, m, a, b);
cout << res.size() << endl;
for (auto x : res) {
for (auto y : x)
cout << y << " ";
cout << endl;
}
for (int i = 0; i < res.size(); ++i)
for (int j = 0; j < res.size(); ++j) {
if (i < (res.size() - 1))
if (!mp[{res[i + 1][j], res[i][j]}] && !mp[{res[i][j], res[i + 1][j]}])
{
cout << "FAIL!"; return 0;
}
if (j < (res.size() - 1))
if (!mp[{res[i][j + 1], res[i][j]}] && !mp[{res[i][j], res[i][j + 1]}])
{
cout << "FAIL!"; return 0;
}
}
cout << "Success!" << endl;
cout << "R = " << (float)res.size() / (float)n << endl;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |