#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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
954 ms |
262144 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
339 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
954 ms |
262144 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
