oj.uz

Submission #954103

# Submission time Handle Problem Language Result Execution time Memory
954103 2024-03-27T09:34:04 Z LucaIlie Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 882 ms 391532 KB 
#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;
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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33116 KB Output is correct
2 Correct 8 ms 33116 KB Output is correct
3 Correct 8 ms 33116 KB Output is correct
4 Correct 7 ms 33116 KB Output is correct
5 Correct 8 ms 33116 KB Output is correct
6 Correct 8 ms 33116 KB Output is correct
7 Correct 8 ms 33116 KB Output is correct
8 Correct 8 ms 33116 KB Output is correct
9 Correct 8 ms 33264 KB Output is correct
10 Correct 8 ms 33112 KB Output is correct
11 Correct 8 ms 33268 KB Output is correct
12 Correct 9 ms 33112 KB Output is correct
13 Correct 9 ms 33116 KB Output is correct
14 Correct 8 ms 33116 KB Output is correct
15 Correct 9 ms 33372 KB Output is correct
16 Correct 8 ms 33116 KB Output is correct
17 Correct 9 ms 33372 KB Output is correct
18 Correct 8 ms 33256 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33116 KB Output is correct
2 Correct 8 ms 33116 KB Output is correct
3 Correct 8 ms 33116 KB Output is correct
4 Correct 7 ms 33116 KB Output is correct
5 Correct 8 ms 33116 KB Output is correct
6 Correct 8 ms 33116 KB Output is correct
7 Correct 8 ms 33116 KB Output is correct
8 Correct 8 ms 33116 KB Output is correct
9 Correct 8 ms 33264 KB Output is correct
10 Correct 8 ms 33112 KB Output is correct
11 Correct 8 ms 33268 KB Output is correct
12 Correct 9 ms 33112 KB Output is correct
13 Correct 9 ms 33116 KB Output is correct
14 Correct 8 ms 33116 KB Output is correct
15 Correct 9 ms 33372 KB Output is correct
16 Correct 8 ms 33116 KB Output is correct
17 Correct 9 ms 33372 KB Output is correct
18 Correct 8 ms 33256 KB Output is correct
19 Correct 35 ms 34316 KB Output is correct
20 Correct 39 ms 34396 KB Output is correct
21 Correct 46 ms 34400 KB Output is correct
22 Correct 44 ms 34940 KB Output is correct
23 Correct 66 ms 38992 KB Output is correct
24 Correct 83 ms 41268 KB Output is correct
25 Correct 93 ms 42328 KB Output is correct
26 Correct 111 ms 43116 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33112 KB Output is correct
2 Correct 8 ms 33116 KB Output is correct
3 Correct 14 ms 33284 KB Output is correct
4 Correct 51 ms 33492 KB Output is correct
5 Correct 198 ms 34228 KB Output is correct
6 Correct 8 ms 33116 KB Output is correct
7 Correct 8 ms 33372 KB Output is correct
8 Correct 8 ms 33232 KB Output is correct
9 Correct 12 ms 33372 KB Output is correct
10 Correct 50 ms 33680 KB Output is correct
11 Correct 221 ms 34640 KB Output is correct
12 Correct 14 ms 34904 KB Output is correct
13 Correct 18 ms 34908 KB Output is correct
14 Correct 19 ms 34908 KB Output is correct
15 Correct 63 ms 35164 KB Output is correct
16 Correct 255 ms 36468 KB Output is correct
17 Correct 180 ms 69008 KB Output is correct
18 Correct 166 ms 68700 KB Output is correct
19 Correct 193 ms 68868 KB Output is correct
20 Correct 237 ms 69236 KB Output is correct
21 Correct 543 ms 70532 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34652 KB Output is correct
2 Correct 57 ms 34992 KB Output is correct
3 Correct 240 ms 35136 KB Output is correct
4 Correct 488 ms 35960 KB Output is correct
5 Correct 101 ms 52420 KB Output is correct
6 Correct 169 ms 52568 KB Output is correct
7 Correct 514 ms 53216 KB Output is correct
8 Correct 882 ms 53964 KB Output is correct
9 Runtime error 376 ms 269440 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 764 ms 391532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33116 KB Output is correct
2 Correct 8 ms 33116 KB Output is correct
3 Correct 8 ms 33116 KB Output is correct
4 Correct 7 ms 33116 KB Output is correct
5 Correct 8 ms 33116 KB Output is correct
6 Correct 8 ms 33116 KB Output is correct
7 Correct 8 ms 33116 KB Output is correct
8 Correct 8 ms 33116 KB Output is correct
9 Correct 8 ms 33264 KB Output is correct
10 Correct 8 ms 33112 KB Output is correct
11 Correct 8 ms 33268 KB Output is correct
12 Correct 9 ms 33112 KB Output is correct
13 Correct 9 ms 33116 KB Output is correct
14 Correct 8 ms 33116 KB Output is correct
15 Correct 9 ms 33372 KB Output is correct
16 Correct 8 ms 33116 KB Output is correct
17 Correct 9 ms 33372 KB Output is correct
18 Correct 8 ms 33256 KB Output is correct
19 Correct 35 ms 34316 KB Output is correct
20 Correct 39 ms 34396 KB Output is correct
21 Correct 46 ms 34400 KB Output is correct
22 Correct 44 ms 34940 KB Output is correct
23 Correct 66 ms 38992 KB Output is correct
24 Correct 83 ms 41268 KB Output is correct
25 Correct 93 ms 42328 KB Output is correct
26 Correct 111 ms 43116 KB Output is correct
27 Correct 9 ms 33112 KB Output is correct
28 Correct 8 ms 33116 KB Output is correct
29 Correct 14 ms 33284 KB Output is correct
30 Correct 51 ms 33492 KB Output is correct
31 Correct 198 ms 34228 KB Output is correct
32 Correct 8 ms 33116 KB Output is correct
33 Correct 8 ms 33372 KB Output is correct
34 Correct 8 ms 33232 KB Output is correct
35 Correct 12 ms 33372 KB Output is correct
36 Correct 50 ms 33680 KB Output is correct
37 Correct 221 ms 34640 KB Output is correct
38 Correct 14 ms 34904 KB Output is correct
39 Correct 18 ms 34908 KB Output is correct
40 Correct 19 ms 34908 KB Output is correct
41 Correct 63 ms 35164 KB Output is correct
42 Correct 255 ms 36468 KB Output is correct
43 Correct 180 ms 69008 KB Output is correct
44 Correct 166 ms 68700 KB Output is correct
45 Correct 193 ms 68868 KB Output is correct
46 Correct 237 ms 69236 KB Output is correct
47 Correct 543 ms 70532 KB Output is correct
48 Correct 16 ms 34652 KB Output is correct
49 Correct 57 ms 34992 KB Output is correct
50 Correct 240 ms 35136 KB Output is correct
51 Correct 488 ms 35960 KB Output is correct
52 Correct 101 ms 52420 KB Output is correct
53 Correct 169 ms 52568 KB Output is correct
54 Correct 514 ms 53216 KB Output is correct
55 Correct 882 ms 53964 KB Output is correct
56 Runtime error 376 ms 269440 KB Execution killed with signal 11
57 Halted 0 ms 0 KB -