Submission #954105

#	Time	Username	Problem	Language	Result	Execution time	Memory
954105		LucaIlie	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	956 ms	392480 KiB

diameter

#include <bits/stdc++.h>

#define int long long

using namespace std;

struct edge {
    int u, v, w;

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

const int MAX_N = 1e5 + 10;
edge edges[MAX_N];
vector<int> adj[MAX_N + 1];

bool isCentroid[MAX_N + 1];
int sz[MAX_N + 1];

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


}

int totSz;
int findCentroid( int u, int p ) {
    int c = 0, maxSz = totSz - sz[u];
    for ( int e: adj[u] ) {
        int v = edges[e].other( u );
        if ( v == p || isCentroid[v] )
            continue;
        int d = findCentroid( v, u );
        if ( d != 0 )
            c = d;
        maxSz = max( maxSz, sz[v] );
    }
    if ( maxSz <= totSz / 2 )
        c = u;
    return c;
}

vector<int> centroids[MAX_N], heads[MAX_N + 1];
unordered_map<int, int> head[MAX_N + 1], leftPos[MAX_N + 1], rightPos[MAX_N + 1];
int crtPos;

void dfs( int u, int p, int c, int h ) {

    int children = 0;
    for ( int e: adj[u] ) {
        int v = edges[e].other( u );
        if ( v == p || isCentroid[v] )
            continue;

        centroids[e].push_back( c );
        head[c][e] = h;
        leftPos[c][e] = crtPos;
        dfs( v, u, c, h );
        rightPos[c][e] = crtPos - 1;
        children++;
    }

    if ( children == 0 )
        crtPos++;
}

void decomp( int r ) {
    calcSizes( r, 0 );
    totSz = sz[r];
    int c = findCentroid( r, 0 );

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

        centroids[e].push_back( c );
        heads[c].push_back( e );
        head[c][e] = e;
        leftPos[c][e] = crtPos;
        dfs( v, c, c, e );
        rightPos[c][e] = crtPos - 1;
    }

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

multiset<int> diameterByCentroid[MAX_N + 1], allDiameters;

struct SegTree {
    int ll, rr;
    int segTree[4 * MAX_N];
    int lazy[4 * MAX_N];

    void propag( int v, int l, int r ) {
        segTree[v] += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void init( int l, int r ) {
        ll = l;
        rr = r;
    }

    void update( int v, int l, int r, int lu, int ru, int x ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] = x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }

    void update( int l, int r, int x ) {
        update( 0, ll, rr, l, r, x );
    }

    int query( int v, int l, int r, int lq, int rq ) {
        if ( l > rq || r < lq )
            return 0;

        if ( lq <= l && r <= rq )
            return segTree[v];

        int mid = (l + r) / 2;
        return max( query( v * 2 + 1, l, mid, lq, rq ), query( v * 2 + 2, mid + 1, r, lq, rq ) );
    }

    int query( int l, int r ) {
        return query( 0, ll, rr, l, r );
    }
} depths;

signed main() {
    int n, q, m;

    cin >> n >> q >> m;
    for ( int e = 0; e < n - 1; e++ ) {
        cin >> edges[e].u >> edges[e].v >> edges[e].w;
        adj[edges[e].u].push_back( e );
        adj[edges[e].v].push_back( e );
    }

    crtPos = 0;
    decomp( 1 );

    depths.init( 0, crtPos - 1 );
    for ( int c = 1; c <= n; c++ ) {
        for ( auto p: head[c] ) {
            int e = p.first;
            depths.update( leftPos[c][e], rightPos[c][e], edges[e].w );
            //printf( "update %d %d %d %d %d\n", c, e, leftPos[c][e], rightPos[c][e], edges[e].w );
        }

        for ( int h: heads[c] ) {
            int maxDepth = depths.query( leftPos[c][h], rightPos[c][h] );
            diameterByCentroid[c].insert( maxDepth );
            //printf( "query %d %d-%d %d %d %d\n", c, edges[h].u, edges[h].v, leftPos[c][h], rightPos[c][h], maxDepth );
        }
       // printf( "\n" );

        int d1 = (diameterByCentroid[c].size() <= 0 ? 0 : *diameterByCentroid[c].rbegin());
        int d2 = (diameterByCentroid[c].size() <= 1 ? 0 : *next( diameterByCentroid[c].rbegin() ) );
        allDiameters.insert( d1 + d2 );
    }

    int last = 0;
    while ( q-- ) {
        int e, w;

        cin >> e >> w;
        e = (e + last) % (n - 1);
        w = (w + last) % m;

        //printf( "%d-%d %d\n", edges[e].u, edges[e].v, w );
        for ( int c: centroids[e] ) {
            int d1, d2, maxDepth;

            //printf( "U %d\n", c );
            d1 = (diameterByCentroid[c].size() <= 0 ? 0 : *diameterByCentroid[c].rbegin());
            d2 = (diameterByCentroid[c].size() <= 1 ? 0 : *next( diameterByCentroid[c].rbegin() ) );
            allDiameters.erase( allDiameters.lower_bound( d1 + d2 ) );
           // printf( "%d %d\n", d1, d2 );

            //for ( int d: diameterByCentroid[c] )
               // printf( "nj %d\n", d );
            //for ( int d: allDiameters )
               // printf( "l %d\n", d );

            int h = head[c][e];
            maxDepth = depths.query( leftPos[c][h], rightPos[c][h] );
            diameterByCentroid[c].erase( diameterByCentroid[c].lower_bound( maxDepth ) );
            depths.update( leftPos[c][e], rightPos[c][e], w - edges[e].w );
            maxDepth = depths.query( leftPos[c][h], rightPos[c][h] );
            diameterByCentroid[c].insert( maxDepth );

            d1 = (diameterByCentroid[c].size() <= 0 ? 0 : *diameterByCentroid[c].rbegin());
            d2 = (diameterByCentroid[c].size() <= 1 ? 0 : *next( diameterByCentroid[c].rbegin() ) );
            allDiameters.insert( d1 + d2 );
        }

        edges[e].w = w;

        last = *allDiameters.rbegin();
        cout << last << "\n";

        //printf( "\n\n\n\n" );
    }

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27