oj.uz

답안 #954130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954130 2024-03-27T10:26:29 Z LucaIlie Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 4889 ms 223152 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

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

int leafs[MAX_N + 1];
vector<int> centroids[MAX_N], heads[MAX_N + 1];
vector<pair<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].push_back( { e, h } );
        leftPos[c].push_back( { e, crtPos } );
        dfs( v, u, c, h );
        rightPos[c].push_back( { e, crtPos - 1 } );
        children++;
    }

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

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

    crtPos = 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].push_back( { e, e } );
        leftPos[c].push_back( { e, crtPos } );
        dfs( v, c, c, e );
        rightPos[c].push_back( { e, crtPos - 1 } );
    }
    sort( head[c].begin(), head[c].end() );
    sort( leftPos[c].begin(), leftPos[c].end() );
    sort( rightPos[c].begin(), rightPos[c].end() );

    leafs[c] = crtPos;

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

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

int findElem( vector<pair<int, int>> &v, int x ) {
    int st = 0, dr = v.size();
    while ( dr - st > 1 ) {
        int mij = (st + dr) / 2;

        if ( v[mij].first > x )
            dr = mij;
        else
            st = mij;
    }
    return v[st].second;
}

struct SegTree {
    int ll, rr;
    vector<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;
        segTree.resize( 4 * (r - l + 1) );
        lazy.resize( 4 * (r - l + 1) );
    }

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

SegTree depths[MAX_N + 1];

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

    decomp( 1 );

    for ( int c = 1; c <= n; c++ ) {
        depths[c].init( 0, leafs[c] - 1 );
        for ( auto p: head[c] ) {
            int e = p.first;
            depths[c].update( findElem( leftPos[c], e ), findElem( rightPos[c], e ), edges[e].w );
        }

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

        long long d1 = (diameterByCentroid[c].size() <= 0 ? 0 : *diameterByCentroid[c].rbegin());
        long long 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] ) {
            long long 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 = findElem( head[c], e );
            maxDepth = depths[c].query( findElem( leftPos[c], h ), findElem( rightPos[c], h ) );
            diameterByCentroid[c].erase( diameterByCentroid[c].lower_bound( maxDepth ) );

            depths[c].update( findElem( leftPos[c], e ), findElem( rightPos[c], e ), w - edges[e].w );

            maxDepth = depths[c].query( findElem( leftPos[c], h ), findElem( 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 9 ms 25436 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 7 ms 25432 KB Output is correct
4 Correct 6 ms 25656 KB Output is correct
5 Correct 8 ms 25408 KB Output is correct
6 Correct 6 ms 25412 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 6 ms 25432 KB Output is correct
10 Correct 6 ms 25432 KB Output is correct
11 Correct 7 ms 25436 KB Output is correct
12 Correct 6 ms 25436 KB Output is correct
13 Correct 6 ms 25436 KB Output is correct
14 Correct 7 ms 25436 KB Output is correct
15 Correct 6 ms 25432 KB Output is correct
16 Correct 7 ms 25436 KB Output is correct
17 Correct 7 ms 25688 KB Output is correct
18 Correct 7 ms 25436 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 25436 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 7 ms 25432 KB Output is correct
4 Correct 6 ms 25656 KB Output is correct
5 Correct 8 ms 25408 KB Output is correct
6 Correct 6 ms 25412 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 6 ms 25432 KB Output is correct
10 Correct 6 ms 25432 KB Output is correct
11 Correct 7 ms 25436 KB Output is correct
12 Correct 6 ms 25436 KB Output is correct
13 Correct 6 ms 25436 KB Output is correct
14 Correct 7 ms 25436 KB Output is correct
15 Correct 6 ms 25432 KB Output is correct
16 Correct 7 ms 25436 KB Output is correct
17 Correct 7 ms 25688 KB Output is correct
18 Correct 7 ms 25436 KB Output is correct
19 Correct 33 ms 25944 KB Output is correct
20 Correct 36 ms 25948 KB Output is correct
21 Correct 39 ms 26360 KB Output is correct
22 Correct 35 ms 25948 KB Output is correct
23 Correct 58 ms 28684 KB Output is correct
24 Correct 70 ms 29020 KB Output is correct
25 Correct 79 ms 29524 KB Output is correct
26 Correct 69 ms 29528 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 9 ms 25436 KB Output is correct
4 Correct 45 ms 25660 KB Output is correct
5 Correct 202 ms 25952 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 6 ms 25692 KB Output is correct
8 Correct 8 ms 25688 KB Output is correct
9 Correct 11 ms 25688 KB Output is correct
10 Correct 53 ms 25764 KB Output is correct
11 Correct 252 ms 26468 KB Output is correct
12 Correct 13 ms 26968 KB Output is correct
13 Correct 13 ms 26868 KB Output is correct
14 Correct 23 ms 26972 KB Output is correct
15 Correct 70 ms 26968 KB Output is correct
16 Correct 306 ms 27500 KB Output is correct
17 Correct 189 ms 52164 KB Output is correct
18 Correct 174 ms 52008 KB Output is correct
19 Correct 190 ms 52116 KB Output is correct
20 Correct 258 ms 52160 KB Output is correct
21 Correct 636 ms 52952 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 26200 KB Output is correct
2 Correct 51 ms 26296 KB Output is correct
3 Correct 231 ms 26460 KB Output is correct
4 Correct 435 ms 26544 KB Output is correct
5 Correct 54 ms 34384 KB Output is correct
6 Correct 118 ms 34492 KB Output is correct
7 Correct 384 ms 34640 KB Output is correct
8 Correct 725 ms 34888 KB Output is correct
9 Correct 287 ms 76472 KB Output is correct
10 Correct 388 ms 76472 KB Output is correct
11 Correct 879 ms 77140 KB Output is correct
12 Correct 1587 ms 76976 KB Output is correct
13 Correct 609 ms 133036 KB Output is correct
14 Correct 757 ms 132860 KB Output is correct
15 Correct 1465 ms 133608 KB Output is correct
16 Correct 2293 ms 133808 KB Output is correct
17 Correct 4889 ms 133944 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 805 ms 223152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 25436 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 7 ms 25432 KB Output is correct
4 Correct 6 ms 25656 KB Output is correct
5 Correct 8 ms 25408 KB Output is correct
6 Correct 6 ms 25412 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 6 ms 25432 KB Output is correct
10 Correct 6 ms 25432 KB Output is correct
11 Correct 7 ms 25436 KB Output is correct
12 Correct 6 ms 25436 KB Output is correct
13 Correct 6 ms 25436 KB Output is correct
14 Correct 7 ms 25436 KB Output is correct
15 Correct 6 ms 25432 KB Output is correct
16 Correct 7 ms 25436 KB Output is correct
17 Correct 7 ms 25688 KB Output is correct
18 Correct 7 ms 25436 KB Output is correct
19 Correct 33 ms 25944 KB Output is correct
20 Correct 36 ms 25948 KB Output is correct
21 Correct 39 ms 26360 KB Output is correct
22 Correct 35 ms 25948 KB Output is correct
23 Correct 58 ms 28684 KB Output is correct
24 Correct 70 ms 29020 KB Output is correct
25 Correct 79 ms 29524 KB Output is correct
26 Correct 69 ms 29528 KB Output is correct
27 Correct 6 ms 25436 KB Output is correct
28 Correct 6 ms 25436 KB Output is correct
29 Correct 9 ms 25436 KB Output is correct
30 Correct 45 ms 25660 KB Output is correct
31 Correct 202 ms 25952 KB Output is correct
32 Correct 6 ms 25436 KB Output is correct
33 Correct 6 ms 25692 KB Output is correct
34 Correct 8 ms 25688 KB Output is correct
35 Correct 11 ms 25688 KB Output is correct
36 Correct 53 ms 25764 KB Output is correct
37 Correct 252 ms 26468 KB Output is correct
38 Correct 13 ms 26968 KB Output is correct
39 Correct 13 ms 26868 KB Output is correct
40 Correct 23 ms 26972 KB Output is correct
41 Correct 70 ms 26968 KB Output is correct
42 Correct 306 ms 27500 KB Output is correct
43 Correct 189 ms 52164 KB Output is correct
44 Correct 174 ms 52008 KB Output is correct
45 Correct 190 ms 52116 KB Output is correct
46 Correct 258 ms 52160 KB Output is correct
47 Correct 636 ms 52952 KB Output is correct
48 Correct 12 ms 26200 KB Output is correct
49 Correct 51 ms 26296 KB Output is correct
50 Correct 231 ms 26460 KB Output is correct
51 Correct 435 ms 26544 KB Output is correct
52 Correct 54 ms 34384 KB Output is correct
53 Correct 118 ms 34492 KB Output is correct
54 Correct 384 ms 34640 KB Output is correct
55 Correct 725 ms 34888 KB Output is correct
56 Correct 287 ms 76472 KB Output is correct
57 Correct 388 ms 76472 KB Output is correct
58 Correct 879 ms 77140 KB Output is correct
59 Correct 1587 ms 76976 KB Output is correct
60 Correct 609 ms 133036 KB Output is correct
61 Correct 757 ms 132860 KB Output is correct
62 Correct 1465 ms 133608 KB Output is correct
63 Correct 2293 ms 133808 KB Output is correct
64 Correct 4889 ms 133944 KB Output is correct
65 Runtime error 805 ms 223152 KB Execution killed with signal 11
66 Halted 0 ms 0 KB -