Submission #940539

#TimeUsernameProblemLanguageResultExecution timeMemory
940539pccVillage (BOI20_village)C++17
100 / 100
77 ms23240 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 1e5+10; vector<int> tree[mxn]; int N; namespace S1{ ll ans; ll dp[mxn]; int mx[mxn]; void dfs(int now,int par){ vector<int> need; dp[now] = 1; for(auto nxt:tree[now]){ if(nxt == par)continue; dfs(nxt,now); if(dp[nxt])need.push_back(nxt); } if(need.size()>=2){ dp[now] = 0; ans += need.size()*2; for(int i = 1;i<need.size();i++){ mx[need[i-1]] = need[i]; } mx[need.back()] = now; mx[now] = need[0]; need.clear(); } else if(need.size() == 1){ dp[now] = 0; ans += 2; int a = need[0]; mx[now] = a; mx[a] = now; } if(now==par&&dp[now]){ ans += 2; int a = tree[now][0],b = mx[a]; while(mx[b] != a)b = mx[b]; mx[now] = a; mx[b] = now; } return; } void solve(){ dfs(1,1); return; } } namespace S2{ int mx[mxn],sz[mxn],dep[mxn]; int arr[mxn]; ll ans = 0; void szdfs(int now,int par){ sz[now] = 1; for(auto nxt:tree[now]){ if(nxt == par)continue; szdfs(nxt,now); sz[now] += sz[nxt]; } return; } int get_centroid(int now,int par,int tar = sz[1]){ for(auto nxt:tree[now]){ if(nxt == par)continue; if(sz[nxt]>(tar-1)/2)return get_centroid(nxt,now,tar); } return now; } vector<vector<int>> v; vector<pii> vp; void dfs(int now,int par){ dep[now] = dep[par]+1; ans += dep[now]*2; v.back().push_back(now); for(auto nxt:tree[now]){ if(nxt == par)continue; dfs(nxt,now); } return; } void solve(){ szdfs(1,1); int cen = get_centroid(1,1); for(auto nxt:tree[cen]){ vp.push_back({0,v.size()}); v.push_back({}); dfs(nxt,cen); vp.back().fs = v.back().size(); } sort(vp.begin(),vp.end()); v[0].push_back(cen); vp[0].sc++; int pt = 0; while(!v.empty()){ arr[pt] = v.back().back(); v.back().pop_back(); if(v.back().empty())v.pop_back(); pt+=2; if(pt>=N)pt = 1; } for(int i = 0;i<N;i++)assert(arr[i]); for(int i = 1;i<N;i++){ mx[arr[i]] = arr[i-1]; } mx[arr[0]] = arr[N-1]; return; } } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N; for(int i = 1;i<N;i++){ int a,b; cin>>a>>b; tree[a].push_back(b); tree[b].push_back(a); } S1::solve(); S2::solve(); cout<<S1::ans<<' '<<S2::ans<<'\n'; for(int i = 1;i<=N;i++)cout<<S1::mx[i]<<' ';cout<<'\n'; for(int i = 1;i<=N;i++)cout<<S2::mx[i]<<' ';cout<<'\n'; return 0; }

Compilation message (stderr)

Village.cpp: In function 'void S1::dfs(int, int)':
Village.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(int i = 1;i<need.size();i++){
      |                  ~^~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:133:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  133 |  for(int i = 1;i<=N;i++)cout<<S1::mx[i]<<' ';cout<<'\n';
      |  ^~~
Village.cpp:133:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  133 |  for(int i = 1;i<=N;i++)cout<<S1::mx[i]<<' ';cout<<'\n';
      |                                              ^~~~
Village.cpp:134:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  134 |  for(int i = 1;i<=N;i++)cout<<S2::mx[i]<<' ';cout<<'\n';
      |  ^~~
Village.cpp:134:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  134 |  for(int i = 1;i<=N;i++)cout<<S2::mx[i]<<' ';cout<<'\n';
      |                                              ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...