Submission #447883

#	Time	Username	Problem	Language	Result	Execution time	Memory
447883		Ozy	Village (BOI20_village)	C++17	50 / 100	104 ms	23884 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;
lli nh[MAX+2],des[MAX+2],dir[MAX+2],desmin[MAX+2];
vector<lli> hijos[MAX+2],orden,nuevo,grande;
lli dp[2][MAX+2];

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 MIN = INF;
    lli nodo;
    lli sum = 0;

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

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

        sum += min(dp[0][h], dp[1][h]);
        if (dp[0][h] == INF) swap(desmin[h], desmin[pos]);
        nodo = h;

    }

    if (nh[pos] == 1) {dp[1][pos]=2;dp[0][pos]=INF;}
    else {
        dp[0][pos] = sum;
        dp[1][pos] = sum+2;
        if (desmin[pos] == pos && pos == 1){
            swap(desmin[nodo], desmin[pos]);
            dp[0][pos] += 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++];
}

void swapea(lli pos, lli padre, lli actual) {

    lli nodo,MIN = INF;
    vector<lli> unos;

    if (pos != 1 && hijos[pos].size() == 1) return;

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

        if (dp[1][h] <= dp[0][h]) {unos.push_back(h); swapea(h,pos,1);}
        else if (dp[1][h]-dp[0][h] < MIN) {MIN = dp[1][h]-dp[0][h]; nodo = h; swapea(h,pos,0);}
    }

    if (actual == 0 && unos.empty()) {unos.push_back(nodo);}
    unos.push_back(pos);
    if (unos.size() == 1) return;

    rep(i,0,unos.size()-2) swap(dir[unos[i]],dir[unos[i+1]]);
}

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;
    rep(i, 1, n) dp[0][i] = INF;

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

    solve();
    ///swapea(1,0,0);

    cout << dp[0][1] << ' '<< 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 DFS(long long int, long long int)':
Village.cpp:35:9: warning: unused variable 'MIN' [-Wunused-variable]
   35 |     lli MIN = INF;
      |         ^~~
Village.cpp: In function 'void solve()':
Village.cpp:80: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]
   80 |         if (menor == -1 || nuevo.size() < menor) menor = nuevo.size();
      |                            ~~~~~~~~~~~~~^~~~~~~
Village.cpp:81: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]
   81 |         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:93:5: note: in expansion of macro 'rep'
   93 |     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:94:5: note: in expansion of macro 'rep'
   94 |     rep(i,0,orden.size()-mayor-1) des[orden[i]] = orden[cont++];
      |     ^~~
Village.cpp: In function 'void swapea(long long int, long long int, long long int)':
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:115:5: note: in expansion of macro 'rep'
  115 |     rep(i,0,unos.size()-2) swap(dir[unos[i]],dir[unos[i+1]]);
      |     ^~~

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