oj.uz

답안 #954110

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954110 2024-03-27T09:47:27 Z LucaIlie Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 5000 ms 268984 KB 
#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v;
    long long 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;
    unordered_map<int, long long> segTree, lazy;

    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, long long 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, long long x ) {
        update( 0, ll, rr, l, r, x );
    }

    long long 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 ) );
    }

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

int main() {
    int n, q;
    long long 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 );
        }

        for ( int h: heads[c] ) {
            int maxDepth = depths.query( leftPos[c][h], rightPos[c][h] );
            diameterByCentroid[c].insert( maxDepth );
        }

        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;
        long long w;

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

        for ( int c: centroids[e] ) {
            int d1, d2, maxDepth;

            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 ) );

            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";
    }

    return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 29272 KB Output is correct
2 Correct 7 ms 29528 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 9 ms 29276 KB Output is correct
5 Correct 7 ms 29304 KB Output is correct
6 Correct 7 ms 29304 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 8 ms 29276 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 7 ms 29276 KB Output is correct
11 Correct 9 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29272 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Correct 8 ms 29308 KB Output is correct
16 Correct 9 ms 29276 KB Output is correct
17 Correct 9 ms 29276 KB Output is correct
18 Correct 8 ms 29276 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 29272 KB Output is correct
2 Correct 7 ms 29528 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 9 ms 29276 KB Output is correct
5 Correct 7 ms 29304 KB Output is correct
6 Correct 7 ms 29304 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 8 ms 29276 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 7 ms 29276 KB Output is correct
11 Correct 9 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29272 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Correct 8 ms 29308 KB Output is correct
16 Correct 9 ms 29276 KB Output is correct
17 Correct 9 ms 29276 KB Output is correct
18 Correct 8 ms 29276 KB Output is correct
19 Correct 68 ms 30556 KB Output is correct
20 Correct 72 ms 30808 KB Output is correct
21 Correct 86 ms 30808 KB Output is correct
22 Correct 80 ms 30812 KB Output is correct
23 Correct 160 ms 37004 KB Output is correct
24 Correct 208 ms 38792 KB Output is correct
25 Correct 262 ms 39948 KB Output is correct
26 Correct 233 ms 39196 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 29272 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 11 ms 29272 KB Output is correct
4 Correct 52 ms 29376 KB Output is correct
5 Correct 236 ms 29640 KB Output is correct
6 Correct 7 ms 29272 KB Output is correct
7 Correct 9 ms 29532 KB Output is correct
8 Correct 9 ms 29532 KB Output is correct
9 Correct 14 ms 29556 KB Output is correct
10 Correct 65 ms 29804 KB Output is correct
11 Correct 305 ms 29912 KB Output is correct
12 Correct 19 ms 31324 KB Output is correct
13 Correct 23 ms 31436 KB Output is correct
14 Correct 27 ms 31324 KB Output is correct
15 Correct 95 ms 31536 KB Output is correct
16 Correct 442 ms 31952 KB Output is correct
17 Correct 357 ms 78436 KB Output is correct
18 Correct 363 ms 78492 KB Output is correct
19 Correct 431 ms 78372 KB Output is correct
20 Correct 482 ms 78620 KB Output is correct
21 Correct 1249 ms 79292 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 31068 KB Output is correct
2 Correct 124 ms 31160 KB Output is correct
3 Correct 544 ms 31736 KB Output is correct
4 Correct 1068 ms 31672 KB Output is correct
5 Correct 291 ms 55336 KB Output is correct
6 Correct 489 ms 55632 KB Output is correct
7 Correct 1556 ms 55912 KB Output is correct
8 Correct 2730 ms 56280 KB Output is correct
9 Correct 1956 ms 180880 KB Output is correct
10 Correct 2579 ms 182088 KB Output is correct
11 Correct 4960 ms 182988 KB Output is correct
12 Execution timed out 5033 ms 182808 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5065 ms 268984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 29272 KB Output is correct
2 Correct 7 ms 29528 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 9 ms 29276 KB Output is correct
5 Correct 7 ms 29304 KB Output is correct
6 Correct 7 ms 29304 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 8 ms 29276 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 7 ms 29276 KB Output is correct
11 Correct 9 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29272 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Correct 8 ms 29308 KB Output is correct
16 Correct 9 ms 29276 KB Output is correct
17 Correct 9 ms 29276 KB Output is correct
18 Correct 8 ms 29276 KB Output is correct
19 Correct 68 ms 30556 KB Output is correct
20 Correct 72 ms 30808 KB Output is correct
21 Correct 86 ms 30808 KB Output is correct
22 Correct 80 ms 30812 KB Output is correct
23 Correct 160 ms 37004 KB Output is correct
24 Correct 208 ms 38792 KB Output is correct
25 Correct 262 ms 39948 KB Output is correct
26 Correct 233 ms 39196 KB Output is correct
27 Correct 7 ms 29272 KB Output is correct
28 Correct 7 ms 29276 KB Output is correct
29 Correct 11 ms 29272 KB Output is correct
30 Correct 52 ms 29376 KB Output is correct
31 Correct 236 ms 29640 KB Output is correct
32 Correct 7 ms 29272 KB Output is correct
33 Correct 9 ms 29532 KB Output is correct
34 Correct 9 ms 29532 KB Output is correct
35 Correct 14 ms 29556 KB Output is correct
36 Correct 65 ms 29804 KB Output is correct
37 Correct 305 ms 29912 KB Output is correct
38 Correct 19 ms 31324 KB Output is correct
39 Correct 23 ms 31436 KB Output is correct
40 Correct 27 ms 31324 KB Output is correct
41 Correct 95 ms 31536 KB Output is correct
42 Correct 442 ms 31952 KB Output is correct
43 Correct 357 ms 78436 KB Output is correct
44 Correct 363 ms 78492 KB Output is correct
45 Correct 431 ms 78372 KB Output is correct
46 Correct 482 ms 78620 KB Output is correct
47 Correct 1249 ms 79292 KB Output is correct
48 Correct 30 ms 31068 KB Output is correct
49 Correct 124 ms 31160 KB Output is correct
50 Correct 544 ms 31736 KB Output is correct
51 Correct 1068 ms 31672 KB Output is correct
52 Correct 291 ms 55336 KB Output is correct
53 Correct 489 ms 55632 KB Output is correct
54 Correct 1556 ms 55912 KB Output is correct
55 Correct 2730 ms 56280 KB Output is correct
56 Correct 1956 ms 180880 KB Output is correct
57 Correct 2579 ms 182088 KB Output is correct
58 Correct 4960 ms 182988 KB Output is correct
59 Execution timed out 5033 ms 182808 KB Time limit exceeded
60 Halted 0 ms 0 KB -