Submission #565815

#TimeUsernameProblemLanguageResultExecution timeMemory
565815shahriarkhanVillage (BOI20_village)C++14
100 / 100
147 ms38732 KiB
#include<bits/stdc++.h> using namespace std ; const int MX = 1e5 + 5 , INF = 1e9 + 5 , LG = 25 ; int dp[MX][2] , mn[MX] ; vector<int> adj[MX] ; vector<pair<int,int> > pick[MX][2] ; void dfs(int s , int p) { int sum = 0 , good = 0 , leaf = 1 , rd = 0 , pos = 0 , idx = 0 ; dp[s][0] = 0 , dp[s][1] = INF ; for(int t : adj[s]) { if(t==p) continue ; dfs(t,s) , leaf = 0 ; dp[s][0] = min(dp[s][0] + dp[t][1] , INF) , pick[s][0].push_back({t,1}) ; if((dp[t][0]+2)<=dp[t][1]) { sum += dp[t][0] + 2 , pick[s][1].push_back({t,0}) , ++pos ; good = 1 ; } else { if(dp[t][0]<dp[t][1]) { rd = t ; idx = pos ; } sum += dp[t][1] , pick[s][1].push_back({t,1}) , ++pos; } } if(!leaf) { if(!good) { if(rd) { pick[s][1].erase(pick[s][1].begin()+idx) ; pick[s][1].push_back({rd,0}) ; sum -= dp[rd][1] ; sum += dp[rd][0] + 2 ; } else { pick[s][1][0].second = 2 ; sum += 2 ; } } dp[s][1] = sum ; } } void build(int s , int c) { if(c==2) c = 1 ; for(pair<int,int> p : pick[s][c]) { build(p.first,p.second) ; if(p.second!=1) swap(mn[p.first],mn[s]) ; } } struct centroid_tree { long long cst = 0 ; int N = 0 ; vector<int> S ; vector<vector<int> > adj ; vector<int> sub , centroid , mx , par ; void init(int n , vector<int> f[]) { N = n ; adj = vector<vector<int> > (n+2) ; sub = vector<int> (n+2,0) ; mx = vector<int> (n+2,0) ; par = vector<int> (n+2,0) ; centroid = vector<int> (n+2,0) ; for(int i = 1 ; i <= n ; ++i) { mx[i] = i ; for(int j : f[i]) { adj[i].push_back(j) ; } } find_ans() ; } void find_siz(int s , int p) { sub[s] = 1 ; for(int t : adj[s]) { if(t==p) continue ; if(centroid[t]) continue ; find_siz(t,s) ; sub[s] += sub[t] ; } for(int t : adj[s]) { if(t==p) continue ; cst += min(sub[t],N-sub[t]) ; } } int find_centroid(int s , int p , int n) { for(int t : adj[s]) { if(t==p) continue ; if(centroid[t]) continue ; if(sub[t]>(n/2)) return find_centroid(t,s,n) ; } return s ; } void topsort(int s , int p) { for(int t : adj[s]) { if(t==p) continue ; topsort(t,s) ; } S.push_back(s) ; } void find_ans() { find_siz(1,0) ; int C = find_centroid(1,0,sub[1]) ; topsort(C,0) ; reverse(S.begin(),S.end()) ; for(int i = 0 ; i < (N/2) ; ++i) { swap(mx[S[i]],mx[S[(i+(N/2))%N]]) ; } if(N&1) swap(mx[S[N/2]],mx[S[N-1]]) ; } }; int main() { int n ; scanf("%d",&n) ; for(int i = 1 ; i < n ; ++i) { int x , y ; scanf("%d%d",&x,&y) ; adj[x].push_back(y) ; adj[y].push_back(x) ; } for(int i = 1 ; i <= n ; ++i) { mn[i] = i ; } dfs(1,0) ; build(1,1) ; centroid_tree C ; C.init(n,adj) ; printf("%d %lld\n",dp[1][1],2*C.cst) ; for(int i = 1 ; i <= n ; ++i) { printf("%d ",mn[i]) ; } printf("\n") ; for(int i = 1 ; i <= n ; ++i) { printf("%d ",C.mx[i]) ; } printf("\n") ; return 0 ; }

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
Village.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         scanf("%d%d",&x,&y) ;
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...