제출 #834252

#제출 시각아이디문제언어결과실행 시간메모리
834252jasminVillage (BOI20_village)C++17
75 / 100
65 ms23460 KiB
//BOI 2020 #include<bits/stdc++.h> using namespace std; int dfsbig(int v, int p, vector<vector<int> >& adi, vector<int>& pre, int n, int& ans){ pre.push_back(v); int s=1; for(auto u: adi[v]){ if(u==p) continue; s+=dfsbig(u, v, adi, pre, n, ans); } ans += 2*min(s, n-s); return s; } bool dfssmall(int v, int p, vector<vector<int> >& adi, vector<int>& go, int& ans, int n){ vector<int> unmatched; for(auto u: adi[v]){ if(u==p) continue; if(dfssmall(u, v, adi, go, ans, n)){ unmatched.push_back(u); } } if(unmatched.empty()){ ans+=2; return true; } unmatched.push_back(v); int s=unmatched.size(); for(int i=0; i<s; i++){ go[unmatched[i]] = unmatched[(i+1)%s]; } return false; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<vector<int> > adi(n); for(int i=0; i<n-1; i++){ int a, b; cin >> a >> b; a--; b--; adi[a].push_back(b); adi[b].push_back(a); } int leaf=-1; for(int i=0; i<n; i++){ if(adi[i].size()==1) leaf=i; } int smallest=0; vector<int> gosmall(n); dfssmall(adi[leaf][0], -1, adi, gosmall, smallest, n); vector<int> pre; int biggest=0; dfsbig(0, -1, adi, pre, n, biggest); vector<int> gobig(n); for(int i=0; i<n; i++){ gobig[pre[i]] = pre[(i+n/2)%n]; } cout << smallest << " " << biggest << "\n"; for(int i=0; i<n; i++){ cout << gosmall[i]+1 << " "; } cout << "\n"; for(int i=0; i<n; i++){ cout << gobig[i]+1 << " "; } cout << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...