oj.uz

답안 #954133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954133 2024-03-27T10:30:20 Z LucaIlie Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 5000 ms 135384 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;
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 );
    }

    long long 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 6 ms 25432 KB Output is correct
2 Correct 6 ms 25400 KB Output is correct
3 Correct 7 ms 25588 KB Output is correct
4 Correct 6 ms 25432 KB Output is correct
5 Correct 6 ms 25432 KB Output is correct
6 Correct 6 ms 25432 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 7 ms 25588 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 7 ms 25572 KB Output is correct
12 Correct 6 ms 25436 KB Output is correct
13 Correct 7 ms 25436 KB Output is correct
14 Correct 6 ms 25436 KB Output is correct
15 Correct 7 ms 25392 KB Output is correct
16 Correct 6 ms 25436 KB Output is correct
17 Correct 6 ms 25436 KB Output is correct
18 Correct 6 ms 25596 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 25432 KB Output is correct
2 Correct 6 ms 25400 KB Output is correct
3 Correct 7 ms 25588 KB Output is correct
4 Correct 6 ms 25432 KB Output is correct
5 Correct 6 ms 25432 KB Output is correct
6 Correct 6 ms 25432 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 7 ms 25588 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 7 ms 25572 KB Output is correct
12 Correct 6 ms 25436 KB Output is correct
13 Correct 7 ms 25436 KB Output is correct
14 Correct 6 ms 25436 KB Output is correct
15 Correct 7 ms 25392 KB Output is correct
16 Correct 6 ms 25436 KB Output is correct
17 Correct 6 ms 25436 KB Output is correct
18 Correct 6 ms 25596 KB Output is correct
19 Correct 34 ms 25948 KB Output is correct
20 Correct 34 ms 26204 KB Output is correct
21 Correct 38 ms 26204 KB Output is correct
22 Correct 34 ms 26204 KB Output is correct
23 Correct 57 ms 28760 KB Output is correct
24 Correct 70 ms 29276 KB Output is correct
25 Correct 79 ms 29788 KB Output is correct
26 Correct 76 ms 29672 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 7 ms 25436 KB Output is correct
3 Correct 10 ms 25436 KB Output is correct
4 Correct 46 ms 25692 KB Output is correct
5 Correct 210 ms 26448 KB Output is correct
6 Correct 5 ms 25436 KB Output is correct
7 Correct 6 ms 25692 KB Output is correct
8 Correct 7 ms 25644 KB Output is correct
9 Correct 12 ms 25692 KB Output is correct
10 Correct 53 ms 25936 KB Output is correct
11 Correct 249 ms 26708 KB Output is correct
12 Correct 16 ms 26968 KB Output is correct
13 Correct 13 ms 26972 KB Output is correct
14 Correct 19 ms 27056 KB Output is correct
15 Correct 72 ms 27260 KB Output is correct
16 Correct 300 ms 28228 KB Output is correct
17 Correct 179 ms 52772 KB Output is correct
18 Correct 174 ms 52908 KB Output is correct
19 Correct 184 ms 52800 KB Output is correct
20 Correct 259 ms 53288 KB Output is correct
21 Correct 618 ms 54176 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 26204 KB Output is correct
2 Correct 52 ms 26392 KB Output is correct
3 Correct 219 ms 26708 KB Output is correct
4 Correct 448 ms 27532 KB Output is correct
5 Correct 52 ms 34640 KB Output is correct
6 Correct 114 ms 34700 KB Output is correct
7 Correct 404 ms 35648 KB Output is correct
8 Correct 739 ms 35736 KB Output is correct
9 Correct 287 ms 77344 KB Output is correct
10 Correct 398 ms 77648 KB Output is correct
11 Correct 893 ms 77920 KB Output is correct
12 Correct 1575 ms 78336 KB Output is correct
13 Correct 616 ms 133960 KB Output is correct
14 Correct 747 ms 134228 KB Output is correct
15 Correct 1425 ms 134896 KB Output is correct
16 Correct 2212 ms 135384 KB Output is correct
17 Correct 4754 ms 135272 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4019 ms 114788 KB Output is correct
2 Correct 4112 ms 116328 KB Output is correct
3 Correct 4062 ms 115472 KB Output is correct
4 Correct 4214 ms 114428 KB Output is correct
5 Correct 4091 ms 109832 KB Output is correct
6 Correct 3559 ms 85036 KB Output is correct
7 Execution timed out 5092 ms 128532 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 25432 KB Output is correct
2 Correct 6 ms 25400 KB Output is correct
3 Correct 7 ms 25588 KB Output is correct
4 Correct 6 ms 25432 KB Output is correct
5 Correct 6 ms 25432 KB Output is correct
6 Correct 6 ms 25432 KB Output is correct
7 Correct 7 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 7 ms 25588 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 7 ms 25572 KB Output is correct
12 Correct 6 ms 25436 KB Output is correct
13 Correct 7 ms 25436 KB Output is correct
14 Correct 6 ms 25436 KB Output is correct
15 Correct 7 ms 25392 KB Output is correct
16 Correct 6 ms 25436 KB Output is correct
17 Correct 6 ms 25436 KB Output is correct
18 Correct 6 ms 25596 KB Output is correct
19 Correct 34 ms 25948 KB Output is correct
20 Correct 34 ms 26204 KB Output is correct
21 Correct 38 ms 26204 KB Output is correct
22 Correct 34 ms 26204 KB Output is correct
23 Correct 57 ms 28760 KB Output is correct
24 Correct 70 ms 29276 KB Output is correct
25 Correct 79 ms 29788 KB Output is correct
26 Correct 76 ms 29672 KB Output is correct
27 Correct 6 ms 25436 KB Output is correct
28 Correct 7 ms 25436 KB Output is correct
29 Correct 10 ms 25436 KB Output is correct
30 Correct 46 ms 25692 KB Output is correct
31 Correct 210 ms 26448 KB Output is correct
32 Correct 5 ms 25436 KB Output is correct
33 Correct 6 ms 25692 KB Output is correct
34 Correct 7 ms 25644 KB Output is correct
35 Correct 12 ms 25692 KB Output is correct
36 Correct 53 ms 25936 KB Output is correct
37 Correct 249 ms 26708 KB Output is correct
38 Correct 16 ms 26968 KB Output is correct
39 Correct 13 ms 26972 KB Output is correct
40 Correct 19 ms 27056 KB Output is correct
41 Correct 72 ms 27260 KB Output is correct
42 Correct 300 ms 28228 KB Output is correct
43 Correct 179 ms 52772 KB Output is correct
44 Correct 174 ms 52908 KB Output is correct
45 Correct 184 ms 52800 KB Output is correct
46 Correct 259 ms 53288 KB Output is correct
47 Correct 618 ms 54176 KB Output is correct
48 Correct 16 ms 26204 KB Output is correct
49 Correct 52 ms 26392 KB Output is correct
50 Correct 219 ms 26708 KB Output is correct
51 Correct 448 ms 27532 KB Output is correct
52 Correct 52 ms 34640 KB Output is correct
53 Correct 114 ms 34700 KB Output is correct
54 Correct 404 ms 35648 KB Output is correct
55 Correct 739 ms 35736 KB Output is correct
56 Correct 287 ms 77344 KB Output is correct
57 Correct 398 ms 77648 KB Output is correct
58 Correct 893 ms 77920 KB Output is correct
59 Correct 1575 ms 78336 KB Output is correct
60 Correct 616 ms 133960 KB Output is correct
61 Correct 747 ms 134228 KB Output is correct
62 Correct 1425 ms 134896 KB Output is correct
63 Correct 2212 ms 135384 KB Output is correct
64 Correct 4754 ms 135272 KB Output is correct
65 Correct 4019 ms 114788 KB Output is correct
66 Correct 4112 ms 116328 KB Output is correct
67 Correct 4062 ms 115472 KB Output is correct
68 Correct 4214 ms 114428 KB Output is correct
69 Correct 4091 ms 109832 KB Output is correct
70 Correct 3559 ms 85036 KB Output is correct
71 Execution timed out 5092 ms 128532 KB Time limit exceeded
72 Halted 0 ms 0 KB -