Submission #770117

#TimeUsernameProblemLanguageResultExecution timeMemory
770117canadavid1Village (BOI20_village)C++17
50 / 100
264 ms58260 KiB
#include <bits/stdc++.h> using namespace std; struct Node { unordered_set<Node*> n; vector<int> leaf; int idx; bool exists = true; void remove() { for(auto i : n) i->n.erase(this); exists = false; } }; /* #define BLOCKSIZE 1024 template<typename T,typename... Args> T* newT(Args... args) { static T* arr = nullptr; static int idx = 0; if(idx == BLOCKSIZE) { arr = new T[BLOCKSIZE]; idx = 0; } T* out = &arr[idx]; out->~T(); idx++; return new(out) T(args ...); }*/ pair<vector<int>,int> doMin(int N, vector<Node>& house) { if(N==2) return {{0,2,1},2}; // prune leaves vector<Node*> leaf; for(int i = 1; i <= N; i++) { house[i].idx = i; if(house[i].n.size()>1) continue; leaf.push_back(&house[i]); } for(auto i : leaf) { (*begin(i->n))->n.erase(i); (*begin(i->n))->leaf.push_back(i->idx); i->exists = false; } vector<Node*> semileaves; for(int i = 1; i <= N; i++) { if (!house[i].exists) continue; if (house[i].n.size()<=1) semileaves.push_back(&house[i]); } vector<int> destinations(N+1); int count=0; while(semileaves.size()) { auto n = semileaves.back(); semileaves.pop_back(); //cerr << "remove semileaf " << n->idx << " with " << n->leaf.size() << " leaves\n"; while(n->leaf.size()>2) { auto l1 = n->leaf.back(); n->leaf.pop_back(); auto l2 = n->leaf.back(); n->leaf.pop_back(); destinations[l1] = l2; destinations[l2] = l1; count += 4; } if(n->leaf.size()==2) { auto l1 = n->leaf.back(); n->leaf.pop_back(); auto l2 = n->leaf.back(); n->leaf.pop_back(); destinations[n->idx] = l1; destinations[l1] = l2; destinations[l2] = n->idx; count += 4; } else { // n->leaf.size() == 1 auto l1 = n->leaf.back(); n->leaf.pop_back(); destinations[n->idx] = l1; destinations[l1] = n->idx; count += 2; } if (n->n.size()==0) continue; auto p = *begin(n->n); p->n.erase(n); if(p->n.size()==1) { if(p->leaf.size()) { // make semileaf semileaves.push_back(p); // done :-) } else { // make leaf auto p2 = *begin(p->n); p->remove(); p2->leaf.push_back(p->idx); if (p2->n.size()==1) semileaves.push_back(p2); } } } return {destinations,count}; } pair<Node*,int> findFurthestNode(Node* s) { queue<pair<Node*,int>> q; q.push({s,0}); Node* p = nullptr; int size; while(q.size()) { tie(s,size) = q.back(); q.pop(); for(auto i : s->n) if (i != p) q.push({i,size+1}); p = s; } return {s,size}; } pair<vector<int>,int> doMax(int N, vector<Node>& house) { if(N==2) return {{0,2,1},2}; for(int i = 1; i <= N; i++) house[i].idx = i; int size = N; Node *aHouse = &house[1]; vector<int> destination(N+1); int count = 0; while(size > 3) { auto[s,ignore] = findFurthestNode(aHouse); auto[t,d] = findFurthestNode(s); destination[s->idx] = t->idx; destination[t->idx] = s->idx; count += 2*d; aHouse = *begin(t->n); s->remove(); t->remove(); size -= 2; } if(size==3) { if(aHouse->n.size()==1) aHouse = *begin(aHouse->n); vector<int> h; for(auto i : aHouse->n) h.push_back(i->idx); destination[h[0]] = h[1]; destination[h[1]] = aHouse->idx; destination[aHouse->idx] = h[0]; count+=4; } else // size==2 { Node *house2 = *begin(aHouse->n); destination[aHouse->idx] = house2->idx; destination[house2->idx] = aHouse->idx; count+=2; } return {destination,count}; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; vector<Node> house(N+1); vector<Node> house2(N+1); for(int i = 1; i < N;i++) { int a,b; cin >> a >> b; house[a].n.insert(&house[b]); house[b].n.insert(&house[a]); house2[a].n.insert(&house2[b]); house2[b].n.insert(&house2[a]); } auto[destinations,count] = doMin(N,house); //auto[destinations2,count2] = doMax(N,house2); vector<int> destinations2(N+1,1); int count2 = 0; cout << count << " " << count2 << "\n"; for(int i = 1; i <= N; i++) cout << destinations[i] << " "; cout << "\n"; for(int i = 1; i <= N; i++) cout << destinations2[i] << " "; cout << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...