Submission #1256252

#TimeUsernameProblemLanguageResultExecution timeMemory
1256252bynixWorld Map (IOI25_worldmap)C++20
72 / 100
69 ms9288 KiB
#include "worldmap.h" #include "bits/stdc++.h" using namespace std; void dfs(int cur, int par, vector<vector<int>>& adj, vector<int>& ord){ ord.push_back(cur); for (auto &e: adj[cur]) if (e != par) { dfs(e, cur, adj, ord); ord.push_back(cur); } } void dfs2(int cur, vector<vector<int>>& adj, vector<int>& vis, vector<vector<int>>& tree){ vis[cur] = 1; for (auto &e: adj[cur]) if (!vis[e]) { tree[cur].push_back(e); tree[e].push_back(cur); dfs2(e, adj, vis, tree); } } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { if (M == 0) return {{1}}; vector<vector<int>> adjM(N+1, vector<int>()), adj(N+1, vector<int>()); int start; for (int i = 0; i < M; i++){ adjM[A[i]].push_back(B[i]); adjM[B[i]].push_back(A[i]); start = A[i]; } vector<int> vis(N+1, 0); dfs2(start, adjM, vis, adj); vector<int> ord; dfs(start, -1, adj, ord); int K = ord.size(); vector<vector<int>> C(2*K, vector<int>(2*K)); for (int i = 0; i < K; i++){ for (int j = 0; j < 2*K; j++) C[2*i][j] = ord[i], C[2*i+1][j] = ord[i]; int d = adjM[ord[i]].size(); for (int k = 0; k < d; k++){ C[2*i][k*2 + i%2] = adjM[ord[i]][k]; if (2*i > 0) C[2*i-1][k*2 + i%2] = ord[i]; } } return C; }
#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...