Submission #1249744

#TimeUsernameProblemLanguageResultExecution timeMemory
1249744flashmtWorld Map (IOI25_worldmap)C++20
72 / 100
68 ms8776 KiB
#include "worldmap.h" #include <bits/stdc++.h> #ifdef LOCAL #include "Debug.h" #else #define debug(...) 42 #endif using namespace std; struct DisjointSet { int n; vector<int> ds, sz; DisjointSet(int n): n(n) { ds = sz = vector<int>(n); for (int i = 0; i < n; i++) { ds[i] = i; sz[i] = 1; } } int get(int x) { return x == ds[x] ? x : ds[x] = get(ds[x]); } int join(int x, int y) { int dx = get(x), dy = get(y); if (dx == dy) return 0; if (sz[dx] < sz[dy]) swap(dx, dy); ds[dy] = dx; sz[dx] += sz[dy]; return 1; } }; const int N = 44; vector<int> a[N]; int depth[N]; void dfs(int x, vector<int> &path) { path.push_back(x); for (int y : a[x]) if (depth[y] < 0) { depth[y] = depth[x] + 1; dfs(y, path); path.push_back(x); } } vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) { for (int &x : A) x--; for (int &x : B) x--; for (int i = 0; i < n; i++) { a[i].clear(); depth[i] = -1; } DisjointSet ds(n); vector<vector<int>> adj(n, vector<int>(n)); for (int i = 0; i < m; i++) { if (ds.join(A[i], B[i])) { a[A[i]].push_back(B[i]); a[B[i]].push_back(A[i]); } adj[A[i]][B[i]] = adj[B[i]][A[i]] = 1; } vector<int> path; depth[0] = 0; dfs(0, path); // trim unnecessary backward edges while (size(path) >= 2) { int x = path[size(path) - 2], y = path[size(path) - 1]; if (depth[x] < depth[y]) break; path.pop_back(); } int len = size(path); int k = max(n * 2, len * 2); debug(path); debug(k); vector<vector<int>> ans(k, vector<int>(k, -1)); for (int i = 0; i < len; i++) { int x = path[i]; if (i % 2 == 0) { for (int row = 0; row < k; row++) if (row % 2 == 0) ans[row][i * 2] = x; else { ans[row][i * 2 + 1] = x; if (i) ans[row][i * 2 - 1] = x; } for (int y = 0; y < k / 2; y++) ans[y * 2 + 1][i * 2] = y < n && adj[x][y] ? y : x; } else { for (int row = 0; row < k; row++) if (row % 2) ans[row][i * 2] = x; else ans[row][i * 2 - 1] = ans[row][i * 2 + 1] = x; for (int y = 0; y < k / 2; y++) ans[y * 2][i * 2] = y < n && adj[x][y] ? y : x; } } for (int i = 0; i < k; i++) for (int &x : ans[i]) if (x < 0) x = path.back() + 1; else x++; return ans; }
#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...