제출 #900510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900510		LucaIlie	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	2822 ms	53248 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
const int INF = 1e8;
int ans[2 * MAX_N + 1];

struct AIB {
    int n;
    vector<int> aib, changes;

    void resize( int _n ) {
        n = _n;
        aib.clear();
        aib.resize( n + 1 );
        for ( int i = 0; i <= n; i++ )
            aib[i] = -INF;
        changes.clear();
    }

    void clear() {
        for ( int i: changes )
            aib[i] = -INF;
        changes.clear();
    }

    void update( int i, int x ) {
        while ( i <= n ) {
            changes.push_back( i );
            aib[i] = max( aib[i], x );
            i += (i & -i);
        }
    }

    int query( int i ) {
        int x = -INF;
        while ( i > 0 ) {
            x = max( aib[i], x );
            i -= (i & -i);
        }
        return x;
    }
};

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<bool> isCentroid;
    vector<int> depth, timeIn, timeOut, subtreeSize, centroidSubtreeSize, centroidDist;
    vector<vector<int>> parent;
    AIB verticesDist;

    void resize( int _size ) {
        n = _size;

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

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

    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 l = lca( u, v );
        return depth[u] + depth[v] - 2 * depth[l];
    }
    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];
    }

    void calcCentroidSizes( int u, int p ) {
        centroidSubtreeSize[u] = 1;
        for ( int e: adj[u] ) {
            int v = edges[e].other( u );
            if ( v == p || isCentroid[v] )
                continue;
            calcCentroidSizes( v, u );
            centroidSubtreeSize[u] += centroidSubtreeSize[v];
        }
    }

    int sizee, centroid;
    void findCentroid( int u, int p ) {
        int maxSize = sizee - centroidSubtreeSize[u];
        for ( int e: adj[u] ) {
            int v = edges[e].other( u );
            if ( v == p || isCentroid[v] )
                continue;
            findCentroid( v, u );
            maxSize = max( maxSize, centroidSubtreeSize[v] );
        }
        if ( maxSize <= sizee / 2 )
            centroid = u;
    }

    vector<int> vertices;
    void compute( int u, int p ) {
        vertices.push_back( u );
        centroidDist[u] = centroidDist[p] + 1;
        for ( int e: adj[u] ) {
            int v = edges[e].other( u );
            if ( v == p || isCentroid[v] )
                continue;
            compute( v, u );
        }
    }

    void decomp( int r ) {
        calcCentroidSizes( r, 0 );
        sizee = centroidSubtreeSize[r];
        findCentroid( r, 0 );
        int c = centroid;

        centroidDist[c] = 0;
        verticesDist.clear();
        for ( int e: adj[c] ) {
            int v = edges[e].other( c );
            if ( isCentroid[v] )
                continue;

            vertices.clear();
            compute( v, c );
            for ( int u: vertices ) {
                int d = dist( u, c ), x = orientedSubtreeSize( u, c ), y = orientedSubtreeSize( c, u );
                ans[min( x, y ) * 2] = max( ans[min( x, y ) * 2], d + 1 );
            }
            for ( int u: vertices )
                ans[orientedSubtreeSize( c, u ) * 2] = max( ans[orientedSubtreeSize( c, u ) * 2], centroidDist[u] + verticesDist.query( n + 1 - orientedSubtreeSize( c, u ) ) + 1 );
            for ( int u: vertices )
                verticesDist.update( n + 1 - orientedSubtreeSize( c, u ), centroidDist[u] );
        }
        reverse( adj[c].begin(), adj[c].end() );
        verticesDist.clear();
        for ( int e: adj[c] ) {
            int v = edges[e].other( c );
            if ( isCentroid[v] )
                continue;

            vertices.clear();
            compute( v, c );
            for ( int u: vertices ) {
                int d = dist( u, c ), x = orientedSubtreeSize( u, c ), y = orientedSubtreeSize( c, u );
                ans[min( x, y ) * 2] = max( ans[min( x, y ) * 2], d + 1 );
            }
            for ( int u: vertices )
                ans[orientedSubtreeSize( c, u ) * 2] = max( ans[orientedSubtreeSize( c, u ) * 2], centroidDist[u] + verticesDist.query( n + 1 - orientedSubtreeSize( c, u ) ) + 1 );
            for ( int u: vertices )
                verticesDist.update( n + 1 - orientedSubtreeSize( c, u ), centroidDist[u] );
        }

        isCentroid[c] = true;
        for ( int e: adj[c] ) {
            int v = edges[e].other( c );
            if ( !isCentroid[v] )
                decomp( v );
        }
    }
};

Tree islands;

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;

    islands.decomp( 1 );

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

    return 0;
}

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