Submission #1244060

#TimeUsernameProblemLanguageResultExecution timeMemory
1244060MalixVillage (BOI20_village)C++20
100 / 100
58 ms20216 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) #define all(x) (x).begin(),(x).end() ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; vii a; vi p,c,s,d; void dfs(int x){ for(auto u:a[x])if(u!=p[x]){ c[x]++; p[u]=x; d[u]=d[x]+1; dfs(u); s[x]+=s[u]; } } int centroid(int x,int y){ for(auto u:a[x])if(s[u]>y/2){ s[x]-=s[u]; s[u]=y; return centroid(u,y); } return x; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n;cin>>n; a.resize(n);p.resize(n,-1);c.resize(n,0);s.resize(n,1);d.resize(n,0); REP(i,0,n-1){ int x,y;cin>>x>>y; x--;y--; a[x].PB(y); a[y].PB(x); } dfs(0); queue<int> q; REP(i,0,n)if(c[i]==0)q.push(i); ll cnt=0,cnt2=0; vi ans(n),ans2(n); REP(i,0,n)ans[i]=i; ans2=ans; while(!q.empty()){ int x=q.front(); q.pop(); if(ans[x]!=x){ if(x!=0){ c[p[x]]--; if(c[p[x]]==0)q.push(p[x]); } continue; } cnt+=2; if(x==0)swap(ans[x],ans[a[0][0]]); else{ swap(ans[x],ans[p[x]]); c[p[x]]--; if(c[p[x]]==0)q.push(p[x]); } } int x=centroid(0,n); p.clear();s.clear();d.clear();c.clear(); p.resize(n,-1);c.resize(n,0);s.resize(n,1);d.resize(n,0); dfs(x); REP(i,0,n)cnt2+=(ll)d[i]*2LL; vi vis(n,0); vis[x]=1; vii b; for(auto u:a[x]){ vi arr; queue<int> q; q.push(u); while(!q.empty()){ int y=q.front(); q.pop(); vis[y]=1; arr.PB(y); for(auto v:a[y])if(!vis[v])q.push(v); } b.PB(arr); } int sz=b.size(); set<pi> ind; REP(i,0,sz)ind.insert({-b[i].size(),i}); while(ind.size()>1){ auto it=ind.begin(); int l=it->S; ind.erase(ind.begin()); it=ind.begin(); int r=it->S; ind.erase(ind.begin()); swap(ans2[b[l].back()],ans2[b[r].back()]); b[l].pop_back(); b[r].pop_back(); if(b[l].size())ind.insert({-b[l].size(),l}); if(b[r].size())ind.insert({-b[r].size(),r}); } if(!ind.empty())swap(ans2[x],ans2[b[ind.begin()->S][0]]); else swap(ans2[x],ans2[(x+1)%n]); cout<<cnt<<" "<<cnt2<<"\n"; for(auto u:ans)cout<<u+1<<" "; cout<<"\n"; for(auto u:ans2)cout<<u+1<<" "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...