Submission #1088103

#TimeUsernameProblemLanguageResultExecution timeMemory
1088103freedommo33Village (BOI20_village)C++17
75 / 100
82 ms60144 KiB
#include <bits/stdc++.h> typedef long long ll; constexpr int M = 1e6+7; using namespace std; vector<vector<int>> g(M); int paramin[M]; int paramax[M]; int par[M]; int sajz[M]; int kolor[M]; int odl[M]; vector<int> preorder; vector<int> kolory[M]; int odl2[20][20]; void bfs(){ queue<int> q; q.push(1); preorder.push_back(1); while(!q.empty()){ int p = q.front(); q.pop(); for(auto i:g[p]) if(par[i] == 0 && par[p]!=i){ q.push(i); par[i] = p; preorder.push_back(i); } } } void bfs2(int v){ queue<int> q; q.push(v); while(!q.empty()){ int p = q.front(); q.pop(); for(auto i:g[p]) if(i != v && odl[i]==0){ odl[i] = odl[p] + 1; q.push(i); } } } int centroid = 0; void dfs(int v){ pair<int, int> maks = {0, 0}; for(auto i:g[v]) if(i!=par[v]){ if(sajz[i] > maks.first) maks = {sajz[i], i}; } if(maks.first > sajz[1]/2) dfs(maks.second); else centroid = v; } void dfs2(int v, int k){ kolor[v] = k; for(auto i:g[v]) if(i!=centroid && kolor[i]==0) dfs2(i, k); } bool czy(vector<int> a, vector<int> b) { return a.size() > b.size(); } void bfs3(int v){ queue<int> q; q.push(v); while(!q.empty()){ int p = q.front(); q.pop(); for(auto i:g[p]) if(odl2[v][i] == 0 && i != v){ odl2[v][i] = odl2[v][p] + 1; q.push(i); } } } int main(){ cin.tie(0)->sync_with_stdio(0); int n; cin>>n; for(int i=1; i<n; i++){ int a, b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } bfs(); reverse(preorder.begin(), preorder.end()); int minwynik = 0; for(auto i:preorder){ sajz[i] = 1; for(auto j:g[i]) if(j!=par[i]) sajz[i] += sajz[j]; int last = 0; int p1 = 0, p2 = 0; for(auto j:g[i]) if(j!=par[i] && paramin[j]==0){ if(last==0) last = j; else{ p1 = last, p2 = j; minwynik += 4; //cout<<"P1: "<<last<<" "<<j<<endl; paramin[last] = j; paramin[j] = last; last = 0; } } if(last!=0){ minwynik += 2; //cout<<"P2: "<<i<<" "<<last<<endl; paramin[i] = last; paramin[last] = i; } else if(p1!=0){ //cout<<"P3: "<<p1<<" "<<p2<<" "<<i<<endl; paramin[p1] = i; paramin[p2] = p1; paramin[i] = p2; } } if(paramin[1] == 0){ bool czy = 0; for(auto i:g[1]){ if(paramin[paramin[i]] == i){ int a = i, b = paramin[a]; //cout<<"P4: "<<a<<" "<<b<<endl; paramin[a] = 1; paramin[b] = a; paramin[1] = b; minwynik+=2; czy = 1; break; } } if(czy == 0){ int a = g[1][0], b = paramin[a], c = paramin[b]; //cout<<"P5: "<<a<<" "<<b<<endl; paramin[b] = c; paramin[c] = b; paramin[1] = a; paramin[a] = 1; minwynik+=2; } } dfs(1); int aktk = 0; for(auto i:g[centroid]) dfs2(i, ++aktk); for(int i=1; i<=n; i++) if(i!=centroid) kolory[kolor[i]].push_back(i); priority_queue<pair<int, int>> q; for(int i=1; i<=aktk; i++){ //cout<<kolory[i].size()<<" "<<i<<endl; q.push({kolory[i].size(), i}); } bfs2(centroid); //for(int i=1; i<=n; i++) cout<<i<<": "<<odl[i]<<endl; int makswyn = 0; while(q.size() > 1){ pair<int, int> a = q.top(); q.pop(); pair<int, int> b = q.top(); q.pop(); int aa = kolory[a.second].back(); kolory[a.second].pop_back(); int bb = kolory[b.second].back(); kolory[b.second].pop_back(); //cout<<"PARUJEMY: "<<aa<<" "<<bb<<endl; makswyn += (odl[aa] + odl[bb])*2; paramax[aa] = bb; paramax[bb] = aa; a.first--, b.first--; if(a.first) q.push(a); if(b.first) q.push(b); } if(!q.empty()){ pair<int, int> a = q.top(); q.pop(); int aa = kolory[a.second].back(); kolory[a.second].pop_back(); //cout<<"PARUJEMY: "<<centroid<<" "<<aa<<endl; makswyn += odl[aa]*2; paramax[centroid] = aa; paramax[aa] = centroid; } if(paramax[centroid] == 0){ int x = 1; if(centroid == 1) x = 2; int a = paramax[x]; paramax[a] = centroid; paramax[centroid] = x; } cout<<minwynik<<" "<<makswyn<<endl; for(int i=1; i<=n; i++) cout<<paramin[i]<<" "; cout<<endl; for(int i=1; i<=n; i++) cout<<paramax[i]<<" "; cout<<endl; //for(int i=1; i<=n; i++) bfs3(i); //int aktmin = 0; //for(int i=1; i<=n; i++) aktmin += odl2[i][paramin[i]]; //int aktmaks = 0; //for(int i=1; i<=n; i++) aktmaks += odl2[i][paramax[i]]; //if(aktmin == minwynik && aktmaks == makswyn) cout<<"OK"<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...