Submission #1250878

#TimeUsernameProblemLanguageResultExecution timeMemory
1250878ByeWorldWorld Map (IOI25_worldmap)C++20
72 / 100
67 ms12872 KiB
#include "worldmap.h" #include <bits/stdc++.h> #define pb push_back #define ll long long #define fi first #define se second using namespace std; typedef pair<int,int> pii; const int MAXN = 2e5+10; int n, m; vector<pii> adj[MAXN]; bool vis[MAXN], use[MAXN]; vector<pii> stac; void dfs(int nw, int pa){ stac.pb({nw, 1}); vis[nw] = 1; for(auto [nx, ed] : adj[nw]){ if(vis[nx]) continue; use[ed] = 1; dfs(nx, nw); } if(pa != 0) stac.pb({pa, 0}); } std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { n = N; m = M; for(int i=0; i<m; i++){ adj[A[i]].pb({B[i], i}); adj[B[i]].pb({A[i], i}); } dfs(1, 0); vector<vector<int>> ans; for(auto [idx, ty] : stac){ vector<int> need; for(auto [nx, ed] : adj[idx]){ if(!use[ed]){ use[ed] = 1; need.pb(nx); } } if(ty==1 && need.size()){ ans.pb({idx}); vector<int> vec; for(auto in : need) vec.pb(idx), vec.pb(in); ans.pb(vec); ans.pb({idx}); } else { ans.pb({idx}); } } int siz = ans.size(); vector<vector<int>> ret; for(auto vec : ans){ vector<int> mas = vec; while(mas.size() < siz) mas.pb(mas[0]); ret.pb(mas); } for(int i=0; i<=max(n, m); i++){ vis[i] = 0; use[i] = 0; adj[i].clear(); } stac.clear(); return ret; }
#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...