Submission #770169

#	Time	Username	Problem	Language	Result	Execution time	Memory
770169		canadavid1	Village (BOI20_village)	C++17	56 / 100	279 ms	57236 KiB

Village

#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);
        n.clear();
        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});
    unordered_set<Node*> v;
    pair<Node*,int> s2;
    int size;
    while(q.size())
    {
        tie(s,size) = q.front(); q.pop();
        if(v.count(s)) continue;
        s2 = {s,size};
        v.insert(s);
        for(auto i : s->n) q.push({i,size+1});
    }
    return s2;
}

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] = N <= 100 ? doMax(N,house2) : pair<vector<int>,int>(vector<int>(N+1,1),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";
    

}

• Subtask 1: 12 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50