Submission #1089630

#TimeUsernameProblemLanguageResultExecution timeMemory
1089630raczekVillage (BOI20_village)C++17
0 / 100
1 ms348 KiB
#include<bits/stdc++.h> using namespace std; #ifdef DEBUG auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";} auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";} #define debug(X) cerr<<"["#X"]: "<<X<<endl; #else #define debug(X) {} #endif vector<int> MinSolve(vector<vector<int> > graph) { int n = graph.size(); vector<int> result(n+1); for(int i=0;i<n+1;i++) result[i] = i; vector<int> par(n+1); vector<int> deg(n+1); queue<int> q; function<void(int, int)> dfs = [&](int a, int fat) { par[a] = fat; for(auto v : graph[a]) if(fat != v) dfs(v, a); deg[a] = graph[a].size(); if(a != 1 && graph[a].size() == 1) q.push(a); }; dfs(1, -1); while(!q.empty()) { int a = q.front(); q.pop(); if(a == 1) continue; if(result[a] == a) swap(result[a], result[par[a]]), result[0]+=2; deg[par[a]]--; if(deg[par[a]] == 1) q.push(par[a]); } if(result[1] == 1) { result[0] += 2; swap(result[graph[1][0]], result[1]); } return result; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin>>n; vector<vector<int> > graph(n+1); for(int i=0;i<n-1;i++) { int a, b; cin>>a>>b; graph[a].push_back(b); graph[b].push_back(a); } vector<int> result = MinSolve(graph); cout<<result[0]<<" "<<0<<"\n"; for(int i=1;i<=n;i++) cout<<result[i]<<" "; cout<<"\n"; for(;n--;) cout<<0<<" "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...