Submission #1123811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123811		LucaIlie	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	474 ms	45812 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
const int MAX_LOG_N = 18;
int n;
int h[MAX_N + 1], p[MAX_N + 1], parent[MAX_N + 1], depth[MAX_N + 1];
int parentLca[MAX_LOG_N + 1][MAX_N + 1];
long long maxDist[MAX_N + 1];
vector<int> adj[MAX_N + 1];

int findParent( int v ) {
    if ( parent[v] == v )
        return v;
    parent[v] = findParent( parent[v] );
    return parent[v];
}

void unionn( int u, int v ) {
    u = findParent( u );
    v = findParent( v );
    if ( h[u] > h[v] )
        swap( u, v );
    parent[u] = v;
}

void dfs( int u, int p ) {
    depth[u] = depth[p] + 1;
    parentLca[0][u] = p;
    for ( int l = 1; l <= log2( n ); l++ )
        parentLca[l][u] = parentLca[l - 1][parentLca[l - 1][u]];
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}

int lca( int u, int v ) {
    if ( depth[u] > depth[v] )
        swap( u, v );

    for ( int l = log2( n ); l >= 0; l-- ) {
        if ( depth[parentLca[l][v]] >= depth[u] )
            v = parentLca[l][v];
    }

    if ( u == v )
        return u;

    for ( int l = log2( n ); l >= 0; l-- ) {
        if ( parentLca[l][u] != parentLca[l][v] ) {
            u = parentLca[l][u];
            v = parentLca[l][v];
        }
    }

    return parentLca[0][u];
}

int dist( int u, int v ) {
    int l = lca( u, v );
    return depth[u] + depth[v] - 2 * depth[l];
}

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

    dfs( 1, 0 );

    for ( int i = 1; i <= n; i++ ) {
        int u = p[i];
        maxDist[u] = 0;
        for ( int v: adj[u] ) {
            if ( h[v] <= h[u] ) {
                v = findParent( v );
                maxDist[u] = max( maxDist[u], maxDist[v] + dist( u, v ) );
                unionn( u, v );
            }
        }
    }

    cout << maxDist[p[n]] << "\n";
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26