Submission #654904

#TimeUsernameProblemLanguageResultExecution timeMemory
654904inksamuraiVillage (BOI20_village)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define rng(i,c,n) for(int i=c;i<n;i++) #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3fm6nhZ ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using pii=pair<int,int>; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} signed main(){ _3fm6nhZ; int n; cin>>n; vec(vi) adj(n); rep(i,n-1){ int u,v; cin>>u>>v; u-=1,v-=1; adj[u].pb(v); adj[v].pb(u); } int ans=0; vi ert(n); auto dfs=[&](auto self,int v,int par)->int{ vi rbts; for(auto u:adj[v]){ if(u==par) continue; int e=self(self,u,v); if(e) rbts.pb(u); } if(sz(rbts)==0) return 1; for(int i=0;i<sz(rbts)-sz(rbts)%2;i+=2){ ert[rbts[i]]=rbts[i+1]; ert[rbts[i+1]]=rbts[i]; ans+=4; } if(sz(rbts)%2){ ert[v]=rbts.back(); ert[rbts.back()]=v; ans+=2; }else{ ert[v]=rbts.back(); ert[rbts.back()]=v; } return (sz(rbts)%2)^1; }; int e=dfs(dfs,0,-1); if(e){ int v=0; { int u=adj[0][0]; int nxt=ert[u]; ert[0]=u; ert[nxt]=0; ans+=2; } } cout<<ans<<" "<<ans<<"\n"; rep(t,2){ rep(i,n)cout<<ert[i]+1<<" "; print(); } }

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:58:7: warning: unused variable 'v' [-Wunused-variable]
   58 |   int v=0;
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...