Submission #769348

#	Time	Username	Problem	Language	Result	Execution time	Memory
769348		canadavid1	Village (BOI20_village)	C++14	50 / 100	177 ms	30464 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);
        exists = false;
    }
};

vector<Node> house;
/*
#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 ...);
}*/

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int N;
    cin >> N;
    house.resize(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]);
    }
    if(N==2) {cout << "2 0\n2 1\n1 1\n";exit(0);}
    // 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);
            }
        }
    }
    cout << count << " 0\n";
    for(int i = 1; i <= N; i++) cout << destinations[i] << " "; cout << "\n";
    for(int i = 1; i <= N; i++) cout << "1 "; cout << "\n";
    

}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:125:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  125 |     for(int i = 1; i <= N; i++) cout << destinations[i] << " "; cout << "\n";
      |     ^~~
Village.cpp:125:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  125 |     for(int i = 1; i <= N; i++) cout << destinations[i] << " "; cout << "\n";
      |                                                                 ^~~~
Village.cpp:126:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  126 |     for(int i = 1; i <= N; i++) cout << "1 "; cout << "\n";
      |     ^~~
Village.cpp:126:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  126 |     for(int i = 1; i <= N; i++) cout << "1 "; cout << "\n";
      |                                               ^~~~

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