Submission #1256312

#TimeUsernameProblemLanguageResultExecution timeMemory
1256312arafatbot144World Map (IOI25_worldmap)C++20
100 / 100
23 ms2884 KiB
#include "worldmap.h" #include <bits/stdc++.h> using namespace std; template <typename T> using v = vector<T>; using pii = pair<int, int>; #define rep(i, k, n) for (int i = k; i < n; i++) v<int> euler; v<bool> vis; v<v<int>> adj; v<int> par; v<int> h; void dfs(int n, int p=-1, int d=0) { //cout << "DFS: " << n << endl; vis[n] = true; par[n] = p; h[n] = d; euler.push_back(n); for (auto x : adj[n]) { if (!vis[x]) { dfs(x, n, d+1); euler.push_back(n); } } } std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { //cout << euler.size() << endl; for (auto x : euler) cout << x << " "; cout << endl; if (M == 0) { return {{1}}; } adj.resize(N); vis.assign(N, false); v<v<int>> grid(N, v<int>(N, 0)); par.assign(N, -1); h.assign(N, 0); rep(i, 0, M) { int a = A[i]; int b = B[i]; a--; b--; adj[a].push_back(b); adj[b].push_back(a); grid[a][b] = 1; grid[b][a] = 1; } dfs(0); int n = 2*N; v<v<int>> f(N, v<int>(n)); rep(i, 0, N) { f[i] = v<int>(n, i+1); int padre = par[i]; if (padre == -1) continue; for (int j = n-h[i]*2; j < n-1; j += 2) { if (padre == -1) continue; f[i][j] = padre+1; f[i][j+1] = padre+1; padre = par[padre]; } } rep(i, 0, N) { for (int j=0;j<n-1; j+=2) { int a = f[i][j]-1; if (a == par[i]) continue; if (par[a] == -1) { if (grid[i][a]) { f[i][j+1] = i+1; } } else { if (grid[i][a]) { if (grid[i][par[a]]) { f[i][j+1] = i+1; } else { f[i][j+1] = i+1; f[i][j+2] = a+1; j += 2; } } } } } v<v<int>> ans(2*N, v<int>(2*N, 1)); rep(i, 0, (int)euler.size()) { ans[i] = f[euler[i]]; } euler.clear(); adj.clear(); grid.clear(); h.clear(); par.clear(); vis.clear(); 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...