Submission #896666

#	Time	Username	Problem	Language	Result	Execution time	Memory
896666		LucaIlie	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	1 ms	512 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

struct Tree {
    struct edge {
        int u, v, c;

        int other( int w ) {
            return u ^ v ^ w;
        }
    };

    int n;
    vector<edge> edges;
    vector<vector<int>> adj;
    vector<int> depth, timeIn, timeOut, subtreeSize;
    vector<vector<int>> parent;

    void resize( int _size ) {
        n = _size;

        edges.clear();
        adj.clear();
        adj.resize( n + 1 );

        depth.clear();
        depth.resize( n + 1 );
        timeIn.clear();
        timeIn.resize( n + 1 );
        timeOut.clear();
        timeOut.resize( n + 1 );
        subtreeSize.clear();
        subtreeSize.resize( n + 1 );
        parent.clear();
        parent.resize( (int)log2( n ) + 1 );
        for ( int i = 0; i <= log2( n ); i++ )
            parent[i].resize( n + 1 );
    }

    void add_edge( int u, int v, int c ) {
        adj[u].push_back( edges.size() );
        adj[v].push_back( edges.size() );
        edges.push_back( { u, v, c } );
    }

    int timee;
    void dfs( int u, int p ) {
        parent[0][u] = p;
        subtreeSize[u] = 1;
        timeIn[u] = ++timee;
        for ( int e: adj[u] ) {
            int v = edges[e].other( u ), c = edges[e].c;
            if ( v == p )
                continue;
            depth[v] = depth[u] + c;
            dfs( v, u );
            subtreeSize[u] += subtreeSize[v];
        }
        timeOut[u] = timee;
    }

    void init( int root ) {
        timee = 0;
        dfs( root, 0 );
        for ( int l = 1; l <= log2( n ); l++ ) {
            for ( int v = 1; v <= n; v++ )
                parent[l][v] = parent[l - 1][parent[l - 1][v]];
        }
    }

    int kthAncestor( int v, int k ) {
        for ( int l = log2( n ); l >= 0; l-- ) {
            if ( k >= (1 << l) ) {
                v = parent[l][v];
                k -= (1 << l);
            }
        }
        return v;
    }

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

        v = kthAncestor( v, depth[v] - depth[u] );
        if ( u == v )
            return v;

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

        return parent[0][v];
    }

    int dist( int u, int v ) {
        int d = 1;

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

        d += depth[v] - depth[u];
        v = kthAncestor( v, depth[v] - depth[u] );
        if ( u == v )
            return d;

        for ( int l = log2( n ); l >= 0; l-- ) {
            if ( parent[l][u] != parent[l][v] ) {
                u = parent[l][u];
                v = parent[l][v];
                d += (2 << l);
            }
        }

        d += 2;
        return d;
    }

    int orientedChild( int v, int u ) {
        return kthAncestor( u, depth[u] - depth[v] - 1 );
    }

    bool inSubtree( int r, int v ) {
        return (timeIn[r] <= timeIn[v]) && (timeOut[v] <= timeOut[r]);
    }

    int orientedSubtreeSize( int r, int v ) {
        if ( inSubtree( v, r ) ) {
            int u = orientedChild( v, r );
            return n - subtreeSize[u];
        }
        return subtreeSize[v];
    }
};

const int MAX_N = 2e5;
Tree islands;
int ans[MAX_N + 1];

int main() {
    int n;

    cin >> n;
    islands.resize( n );
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        islands.add_edge( u, v, 1 );
    }
    islands.init( 1 );

    for ( int i = 1; i <= n; i++ )
        ans[i] = 1;
    for ( int u = 1; u <= n; u++ ) {
        for ( int v = u + 1; v <= n; v++ ) {
            int d = islands.dist( u, v ), x = islands.orientedSubtreeSize( u, v ), y = islands.orientedSubtreeSize( v, u );
            ans[min( x, y ) * 2] = max( ans[min( x, y ) * 2], d );
        }
    }

    for ( int i = n - 2; i >= 1; i -= 2 )
        ans[i] = max( ans[i], ans[i + 2] );
    for ( int i = 1; i <= n; i++ )
        cout << ans[i] << "\n";

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80