Submission #447888

#	Time	Username	Problem	Language	Result	Execution time	Memory
447888		Ozy	Village (BOI20_village)	C++17	100 / 100	95 ms	19356 KiB

Village

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define INF 1000000000000
#define MAX 100000

lli n,a,b,M,cent, summin;
lli nh[MAX+2],des[MAX+2],dir[MAX+2],desmin[MAX+2];
vector<lli> hijos[MAX+2],orden,nuevo,grande;

lli Find(lli pos, lli padre,lli mitad) {

    lli grande = -1;
    for(auto h : hijos[pos]) {
        if (padre == h) continue;
        if (nh[h] > mitad) grande = h;
    }

    if (grande == -1) return pos;
    else return Find(grande,pos,mitad);

}

void DFS(lli pos, lli padre) {

    nh[pos] = 1;
    vector<lli> unos;
    lli nodo;

    for (auto h : hijos[pos]) {
        if (h == padre) continue;

        DFS(h,pos);
        nh[pos] += nh[h];

        if (nh[h] == 1 || desmin[h] == h){
            swap(desmin[h], desmin[pos]);
            summin += 2;
        }
        nodo = h;
    }

    if (desmin[pos] == pos && pos == 1){
        swap(desmin[nodo], desmin[pos]);
        summin += 2;
    }

    lli x = min(nh[pos],n-nh[pos]);
    M += x*2;
}

void agrega(lli pos, lli padre) {
    nuevo.push_back(pos);
    for (auto h : hijos[pos]) if (h != padre) agrega(h,pos);
}

void solve() {

    lli menor,mayor;
    menor = mayor = -1;
    orden.push_back(cent);

    for (auto h : hijos[cent]) {
        nuevo.clear();
        agrega(h,cent);

        if (menor == -1 || nuevo.size() < menor) menor = nuevo.size();
        if (mayor == -1 || nuevo.size() > mayor) {
            swap(nuevo,grande);
            mayor = grande.size();
        }

        if (nuevo.empty()) continue;
        for (auto act : nuevo) orden.push_back(act);
    }

    for (auto act : grande) orden.push_back(act);
    lli cont = 0;

    rep(i,orden.size()-mayor,orden.size()-1) des[orden[i]] = orden[cont++];
    rep(i,0,orden.size()-mayor-1) des[orden[i]] = orden[cont++];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
        dir[i] = i;
    }
    dir[n] = n;
    rep(i, 1, n) desmin[i] = i;

    DFS(1,0);
    cent = Find(1,0,n/2);

    solve();

    cout << summin << ' '<< M <<endl;
    rep(i,1,n) cout << desmin[i] << ' ';
    cout << "\n";
    rep(i,1,n) cout << des[i] << ' ';

}

Compilation message (stderr)

Village.cpp: In function 'void solve()':
Village.cpp:73:41: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   73 |         if (menor == -1 || nuevo.size() < menor) menor = nuevo.size();
      |                            ~~~~~~~~~~~~~^~~~~~~
Village.cpp:74:41: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   74 |         if (mayor == -1 || nuevo.size() > mayor) {
      |                            ~~~~~~~~~~~~~^~~~~~~
Village.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
Village.cpp:86:5: note: in expansion of macro 'rep'
   86 |     rep(i,orden.size()-mayor,orden.size()-1) des[orden[i]] = orden[cont++];
      |     ^~~
Village.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
Village.cpp:87:5: note: in expansion of macro 'rep'
   87 |     rep(i,0,orden.size()-mayor-1) des[orden[i]] = orden[cont++];
      |     ^~~

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