Submission #258881

#TimeUsernameProblemLanguageResultExecution timeMemory
258881easruiVillage (BOI20_village)C++14
0 / 100
2 ms2688 KiB
#include <bits/stdc++.h> #define va first #define vb second #define all(x) (x).begin(), (x).end() using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<pii,int> ppi; typedef pair<int,pii> pip; const int MN = 1e5+5; const int MOD = 1e9+7; const int INF = 1e9; ll sz[MN],N,min_ans,max_ans,cnt; int ord[MN],vmin[MN],vmax[MN]; vector<int> G[MN]; bool vis[MN],done[MN]; void dfs(int s) { vis[s] = 1; sz[s] = 1; for(int e:G[s]){ if(vis[e]) continue; dfs(e); sz[s] += sz[e]; if(done[e]) continue; else{ done[s] = 1; swap(vmin[s],vmin[e]); min_ans += 2; } } if(s!=1) max_ans += min(sz[s],N-sz[s])*2; else if(!done[s]){ swap(vmin[s],vmin[G[s][0]]); min_ans += 2; } } void get(int s, int p) { ord[++cnt] = s; for(int e:G[s]){ if(e==p) continue; get(e,s); } } int main() { ios_base::sync_with_stdio(0),cin.tie(0); cin >> N; for(int i=1; i<N; i++){ int s,e; cin >> s >> e; G[s].push_back(e); G[e].push_back(s); } for(int i=1; i<=N; i++) vmin[i] = i; dfs(1); int s = 1, p = 0; while(1){ bool ch = 0; for(int e:G[s]){ if(e==p) continue; if(sz[e]>N/2){ ch = 1; p = s; s = e; break; } } if(!ch) break; } ord[0] = s; for(int e:G[s]) get(e,s); for(int i=1; i<=N; i++){ vmax[i] = ord[(i+N/2)%N]; } cout << min_ans << ' ' << max_ans << '\n'; for(int i=1; i<=N; i++) cout << vmin[i] << ' '; cout << '\n'; //for(int i=1; i<=N; i++) cout << vmax[i] << ' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...