Submission #946115

#	Time	Username	Problem	Language	Result	Execution time	Memory
946115		LucaIlie	Village (BOI20_village)	C++17	56 / 100	97 ms	16668 KiB

Village

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
int sizee[MAX_N + 1], depth[MAX_N + 1], pairMinn[MAX_N + 1], pairMaxx[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int n;

int c;
void findCentroid( int u, int p ) {
    int maxSizee = 0;
    sizee[u] = 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        findCentroid( v, u );
        sizee[u] += sizee[v];
        maxSizee = max( maxSizee, sizee[v] );
    }
    maxSizee = max( maxSizee, n - sizee[u] );
    if ( maxSizee <= n / 2 )
        c = u;
}

void calcSizes( int u, int p ) {
    sizee[u] = 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        calcSizes( v, u );
        sizee[u] += sizee[v];
    }
}

long long maxSumDist;
vector<int> vert;
void calcDepths( int u, int p ) {
    depth[u] = depth[p] + 1;
    maxSumDist += 2 * depth[u];
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        calcDepths( v, u );
    }
    vert.push_back( u );
}

void getMaxSumDist() {
    depth[0] = -1;
    calcDepths( c, 0 );
    for ( int i = 0; i < n / 2; i++ ) {
        pairMaxx[vert[i]] = vert[n / 2 + i];
        pairMaxx[vert[n / 2 + i]] = vert[i];
    }

    if ( pairMaxx[c] == 0 ) {
        int a = adj[c][0], b = pairMaxx[a];
        pairMaxx[a] = b;
        pairMaxx[b] = c;
        pairMaxx[c] = a;
    }
}

long long minSumDist;
void dfs( int u, int p ) {
    vector<int> unpaired;
    sizee[u] = 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
        sizee[u] += sizee[v];
        if ( pairMinn[v] == 0 )
            unpaired.push_back( v );
    }
    if ( unpaired.size() >= 1 ) {
        unpaired.push_back( u );
        for ( int i = 0; i < (int)unpaired.size(); i++ )
            pairMinn[unpaired[i]] = unpaired[(i + 1) % unpaired.size()];
        minSumDist += 2 * (unpaired.size() - 1);
    }
}

void getMinSumDist() {
    minSumDist = 0;
    dfs( c, 0 );
    if ( pairMinn[c] == 0 ) {
        int a = adj[c][0];
        for ( int v: adj[c] ) {
            if ( sizee[v] % 2 == 1 )
                a = v;
        }
        int b = pairMinn[a];
        pairMinn[a] = b;
        pairMinn[b] = c;
        pairMinn[c] = a;
        if ( sizee[a] % 2 == 0 )
            minSumDist += 2;
    }
}

int main() {
    cin >> n;
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    findCentroid( 1, 0 );
    getMinSumDist();
    getMaxSumDist();

    cout << minSumDist << " " << maxSumDist << "\n";
    for ( int v = 1; v <= n; v++ )
        cout << pairMinn[v] << " ";
    cout << "\n";
    for ( int v = 1; v <= n; v++ )
        cout << pairMaxx[v] << " ";
    cout << "\n";

    return 0;
}

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