Submission #1250235

#TimeUsernameProblemLanguageResultExecution timeMemory
1250235chithanhnguyenWorld Map (IOI25_worldmap)C++20
72 / 100
72 ms9544 KiB
#include "worldmap.h" #include <bits/stdc++.h> using namespace std; int n, m; vector<int> euler_tour; vector<int> spantree[45], adj[45]; bool vis[45], used[45]; void dfs(int u) { vis[u] = 1; for (int v : adj[u]) { if (!vis[v]) { spantree[u].push_back(v); spantree[v].push_back(u); dfs(v); } } } void dfs_euler(int u) { vis[u] = 1; euler_tour.push_back(u); for (int v : adj[u]) { if (!vis[v]) { dfs_euler(v); euler_tour.push_back(u); } } } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { euler_tour.clear(); for (int i = 0; i < 45; ++i) adj[i].clear(); for (int i = 0; i < 45; ++i) spantree[i].clear(); memset(vis, 0, sizeof vis); n = N; m = M; for (int i = 0; i < m; ++i) { int u = A[i], v = B[i]; adj[u].push_back(v); adj[v].push_back(u); } dfs(1); memset(vis, 0, sizeof vis); // for (int i = 1; i <= N; ++i) { // cout << i << ": "; // for (int j : spantree[i]) cout << j << " "; // cout << '\n'; // } dfs_euler(1); // for (int v : euler_tour) cout << v << " "; // cout << '\n'; vector<vector<int>> res(4*n, vector<int>(4*n, 0)); memset(used, 0, sizeof used); int matsz = 4 * n, toursz = 2 * n - 1; int currow = 0; for (int i = 0; i < toursz; ++i) { for (int j = 0; j < matsz; ++j) res[currow][j] = euler_tour[i]; ++currow; if (!used[euler_tour[i]]){ // cout << "Need added at index: " << i << " with: "; for (int j = 0; j < matsz; ++j) res[currow + 1][j] = euler_tour[i]; for (int j = 0; j < matsz; ++j) res[currow][j] = euler_tour[i]; int curcol = 0; for (int v : adj[euler_tour[i]]) { res[currow][curcol] = v; res[currow][curcol + 1] = euler_tour[i]; // cout << v << " "; curcol += 2; } // cout << '\n'; currow += 2; } used[euler_tour[i]] = 1; } for (int i = 0; i < 4 * n; ++i) { for (int j = 0; j < 4 * n; ++j) { if (res[i][j] == 0) res[i][j] = 1; } } // for (int i = 0; i < 4 * n; ++i) { // for (int j = 0; j < 4 * n; ++j) { // cout << res[i][j] << " "; // } // cout << '\n'; // } return res; } // int main() { // vector<vector<int>> res = create_map(4, 4, {1, 1, 2, 3}, {2, 3, 4, 4}); // for (int i = 0; i < 4 * n ; ++i) { // for (int j = 0; j < 4 * n; ++j) { // cout << res[i][j] << " "; // } // cout << '\n'; // } // }
#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...