Submission #914921

#TimeUsernameProblemLanguageResultExecution timeMemory
914921asdasdqwerVillage (BOI20_village)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t signed main() { ios::sync_with_stdio(false); cin.tie(0); int n;cin>>n; vector<set<int>> g(n); vector<vector<int>> bck(n); vector<int> dg(n,0); for (int i=1;i<n;i++) { int a,b;cin>>a>>b;a--;b--; g[a].insert(b); g[b].insert(a); bck[a].push_back(b); bck[b].push_back(a); dg[a]++;dg[b]++; } queue<int> q; vector<bool> vis(n, false); for (int i=0;i<n;i++) { if (dg[i]==1){ q.push(i); vis[i]=true; } } int ans=0; vector<int> conf(n,0); for (int i=0;i<n;i++) { conf[i]=i; } vector<bool> swp(n, false); while (!q.empty()) { int t=q.front();q.pop(); // cout<<t<<"\n"; cout.flush(); if (g[t].size() == 0) { if (!swp[conf[t]]) { swap(conf[t], conf[bck[t][0]]); swp[conf[t]]=true; // cout<<conf[t]+1<<" "<<conf[bck[t][0]]+1<<" bb\n"; ans += 2; } continue; } int ne = *g[t].begin(); vis[ne]=true; if (g[ne].find(t) != g[ne].end()) g[ne].erase(g[ne].find(t)); for (int x:g[ne]) { if (g[x].find(ne) != g[x].end()) g[x].erase(g[x].find(ne)); dg[x]--; if (dg[x]<=1 && !vis[x]) { q.push(x); vis[x]=true; } } if (!swp[ne] && !swp[t]) { dg[ne]--; ans+=2; swap(conf[ne], conf[t]); swp[ne]=swp[t]=true; // cout<<conf[ne]+1<<" "<<conf[t]+1<<"\n"; } } cout<<ans<<"\n"; for (int x:conf) { cout<<x+1<<" "; } cout<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...