Submission #1263104

#TimeUsernameProblemLanguageResultExecution timeMemory
1263104am_aadvikWorld Map (IOI25_worldmap)C++20
86 / 100
60 ms9340 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...