oj.uz

Submission #769344

# Submission time Handle Problem Language Result Execution time Memory
769344 2023-06-29T12:39:23 Z canadavid1 Village (BOI20_village) C++14
19 / 100
 2 ms 600 KB 
#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]);
    }
    
    // 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

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
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Partially correct 0 ms 212 KB Partially correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 340 KB Partially correct
2 Partially correct 1 ms 340 KB Partially correct
3 Partially correct 1 ms 380 KB Partially correct
4 Partially correct 1 ms 596 KB Partially correct
5 Partially correct 1 ms 596 KB Partially correct
6 Partially correct 1 ms 596 KB Partially correct
7 Partially correct 1 ms 468 KB Partially correct
8 Partially correct 1 ms 468 KB Partially correct
9 Partially correct 1 ms 468 KB Partially correct
10 Partially correct 2 ms 596 KB Partially correct
11 Partially correct 1 ms 596 KB Partially correct
12 Partially correct 1 ms 596 KB Partially correct
13 Partially correct 1 ms 596 KB Partially correct
14 Partially correct 1 ms 596 KB Partially correct
15 Partially correct 1 ms 468 KB Partially correct
16 Partially correct 1 ms 600 KB Partially correct
17 Partially correct 1 ms 596 KB Partially correct
18 Partially correct 1 ms 596 KB Partially correct
19 Partially correct 1 ms 596 KB Partially correct
20 Partially correct 1 ms 596 KB Partially correct
21 Partially correct 1 ms 596 KB Partially correct
22 Partially correct 1 ms 596 KB Partially correct
23 Partially correct 1 ms 468 KB Partially correct
24 Partially correct 1 ms 468 KB Partially correct
25 Partially correct 1 ms 340 KB Partially correct
26 Partially correct 1 ms 468 KB Partially correct
27 Partially correct 1 ms 468 KB Partially correct
28 Partially correct 1 ms 596 KB Partially correct
29 Partially correct 1 ms 596 KB Partially correct
30 Partially correct 1 ms 596 KB Partially correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Partially correct 0 ms 212 KB Partially correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -