Submission #254983

#TimeUsernameProblemLanguageResultExecution timeMemory
254983kimbj0709Village (BOI20_village)C++14
100 / 100
184 ms21156 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define maxn 100050 #define f first #define s second vector<vector<int> > adj(maxn); vector<int> subtree_size(maxn,0); vector<int> pos(maxn,0); int currcnt = 1; int n,input1,input2; int centroid = 0; void dfs1(int node,int parent){//used to find subtree size subtree_size[node] = 1; pos[node] = currcnt; currcnt++; for(auto k:adj[node]){ if(k==parent){ continue; } dfs1(k,node); subtree_size[node] += subtree_size[k]; } return; } vector<int> reroute(maxn,1); int mindist = 0; void dfs2(int node,int parent){//used to find optimal ordering for(auto k:adj[node]){ if(k==parent){ continue; } dfs2(k,node); } if(reroute[node]==node&&parent!=-1){ swap(reroute[node],reroute[parent]); mindist++; } if(reroute[node]==node&&parent==-1){ swap(reroute[node],reroute[adj[node][0]]); mindist++; } return; } vector<int> dist(maxn,0); void dfs3(int node,int parent,int distt){ dist[node] = distt; for(auto k:adj[node]){ if(k!=parent){ dfs3(k,node,distt+1); } } } void dfs4(int node,int parent){ bool can = 1; for(auto k:adj[node]){ if(k!=parent){ dfs4(k,node); if(subtree_size[k]>(n/2)){ can = 0; } } } if(n-subtree_size[node]>(n/2)){ can = 0; } if(can){ centroid = node; } } int maxdist = 0; void dfs5(int node,int parent){ for(auto k:adj[node]){ if(k!=parent){ dfs5(k,node); maxdist += subtree_size[k]; } } } vector<int> nodes(maxn); vector<int> ipos(maxn*2); int position = 0; void dfs6(int node,int parent){ ipos[position] = node; ipos[position+n] = node; nodes[node] = position; position++; for(auto k:adj[node]){ if(k!=parent){ dfs6(k,node); } } } vector<int> arrangement(maxn,0); int32_t main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); for(int i=0;i<maxn;i++){ reroute[i] = i; } cin >> n; for(int i=0;i<n-1;i++){ cin >> input1 >> input2; adj[input1].push_back(input2); adj[input2].push_back(input1); } int root = -1; for(int i=1;i<=n;i++){ if(adj[i].size()==(int)1){ root = i; } } dfs1(root,-1); dfs2(root,-1); dfs4(root,-1); dfs1(centroid,-1); dfs5(centroid,-1); int tt = 0; dfs6(centroid,-1); for(int i=1;i<=n;i++){ arrangement[ipos[nodes[i]+(n/2)]] = i; } cout << mindist*2 << " " << maxdist*2 << "\n"; for(int i=1;i<=n;i++){ cout << reroute[i] << " "; //cout << i << " "; } cout << "\n"; for(int i=1;i<=n;i++){ //cout << 1 << " "; cout << arrangement[i] << ' '; //cout << i << " "; } }

Compilation message (stderr)

Village.cpp: In function 'int32_t main()':
Village.cpp:118:9: warning: unused variable 'tt' [-Wunused-variable]
     int tt = 0;
         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...