oj.uz

Submission #946003

# Submission time Handle Problem Language Result Execution time Memory
946003 2024-03-14T09:29:02 Z LucaIlie Village (BOI20_village) C++17
6 / 100
 1 ms 2652 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
int sizee[MAX_N + 1], depth[MAX_N + 1], pairr[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;
vector<int> vertStack;
void dfs( int u, int p ) {
    vert.push_back( u );
    depth[u] = depth[p] + 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}

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 );

    calcSizes( c, 0 );
    sort( adj[c].begin(), adj[c].end(), []( int u, int v ) {
        return sizee[u] > sizee[v];
    } );

    maxSumDist = 0;
    for ( int u: adj[c] ) {
        vert.clear();
        dfs( u, c );

        vector<int> add;
        for ( int v: vert ) {
            if ( !vertStack.empty() ) {
                pairr[v] = vertStack.back();
                pairr[vertStack.back()] = v;
                vertStack.pop_back();
            } else
                add.push_back( v );
            maxSumDist += depth[v];
        }
        for ( int v: add )
            vertStack.push_back( v );
    }
    if ( vertStack.empty() ) {
        int a = adj[c][0], b = pairr[a];
        pairr[a] = b;
        pairr[b] = c;
        pairr[c] = a;
    } else {
        pairr[c] = vertStack.back();
        pairr[vertStack.back()] = c;
        vertStack.pop_back();
    }

    cout << 1 << " " << 2 * maxSumDist << "\n";
    for ( int v = 1; v <= n; v++ )
        cout << v << " ";
    cout << "\n";
    for ( int v = 1; v <= n; v++ )
        cout << pairr[v] << " ";
    cout << "\n";

    return 0;
}

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2652 KB Partially correct
2 Partially correct 1 ms 2652 KB Partially correct
3 Partially correct 1 ms 2652 KB Partially correct
4 Partially correct 1 ms 2652 KB Partially correct
5 Partially correct 1 ms 2652 KB Partially correct
6 Partially correct 1 ms 2652 KB Partially correct
7 Partially correct 1 ms 2652 KB Partially correct
8 Partially correct 1 ms 2652 KB Partially correct
9 Partially correct 1 ms 2652 KB Partially correct
10 Partially correct 1 ms 2652 KB Partially correct
11 Partially correct 1 ms 2652 KB Partially correct
12 Partially correct 1 ms 2652 KB Partially correct
13 Partially correct 1 ms 2652 KB Partially correct
14 Partially correct 1 ms 2652 KB Partially correct
15 Partially correct 1 ms 2652 KB Partially correct
16 Partially correct 1 ms 2648 KB Partially correct
17 Partially correct 1 ms 2652 KB Partially correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Integer parameter [name=vi] equals to 0, violates the range [1, 256]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2652 KB Partially correct
2 Partially correct 1 ms 2652 KB Partially correct
3 Partially correct 1 ms 2652 KB Partially correct
4 Partially correct 1 ms 2652 KB Partially correct
5 Partially correct 1 ms 2652 KB Partially correct
6 Partially correct 1 ms 2652 KB Partially correct
7 Partially correct 1 ms 2652 KB Partially correct
8 Partially correct 1 ms 2652 KB Partially correct
9 Partially correct 1 ms 2652 KB Partially correct
10 Partially correct 1 ms 2652 KB Partially correct
11 Partially correct 1 ms 2652 KB Partially correct
12 Partially correct 1 ms 2652 KB Partially correct
13 Partially correct 1 ms 2652 KB Partially correct
14 Partially correct 1 ms 2652 KB Partially correct
15 Partially correct 1 ms 2652 KB Partially correct
16 Partially correct 1 ms 2648 KB Partially correct
17 Partially correct 1 ms 2652 KB Partially correct
18 Incorrect 1 ms 2652 KB Integer parameter [name=vi] equals to 0, violates the range [1, 256]
19 Halted 0 ms 0 KB -