oj.uz

답안 #954180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954180 2024-03-27T11:07:53 Z LucaIlie Dynamic Diameter (CEOI19_diameter) C++17
11 / 100
 2230 ms 1048576 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];

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 ) {
        propag( v, l, r );

        if ( l > rq || r < lq )
            return 0;

        if ( segTree[v] == 0 )
            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 queryAll() {
        return segTree[0];
    }
};

SegTree depths[2 * 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;
}

struct info {
    int c, h, l, r;
};

vector<info> centroids[MAX_N];
vector<int> heads[MAX_N + 1];
int crtPos, headId;

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;

        info x;
        x.c = c;
        x.h = headId;
        x.l = crtPos;
        dfs( v, u, c, h );
        x.r = crtPos - 1;
        children++;

        centroids[e].push_back( x );
    }

    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;

        heads[c].push_back( headId );

        info x;
        x.c = c;
        x.h = headId;
        x.l = 0;
        dfs( v, c, c, e );
        x.r = crtPos - 1;
        centroids[e].push_back( x );
        depths[headId].init( 0, crtPos - 1 );
        headId++;
    }

    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 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 e = 0; e < n - 1; e++ ) {
        int w = edges[e].w;

        for ( auto x: centroids[e] ) {
            int c = x.c, h = x.h, l = x.l, r = x.r;
            depths[h].update( l, r, w );
        }
    }
    for ( int c = 1; c <= n; c++ ) {
        for ( int h: heads[c] )
            diameterByCentroid[c].insert( depths[h].queryAll() );
        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 ( auto x: centroids[e] ) {
            long long d1, d2, maxDepth;
            int c = x.c, h = x.h, l = x.l, r = x.r;

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

            maxDepth = depths[h].queryAll();
            diameterByCentroid[c].erase( diameterByCentroid[c].lower_bound( maxDepth ) );

            depths[h].update( l, r, w - edges[e].w );

            maxDepth = depths[h].queryAll();
            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;
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:197:17: warning: unused variable 'c' [-Wunused-variable]
  197 |             int c = x.c, h = x.h, l = x.l, r = x.r;
      |                 ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 23384 KB Output is correct
2 Correct 7 ms 23388 KB Output is correct
3 Correct 5 ms 23644 KB Output is correct
4 Correct 8 ms 23388 KB Output is correct
5 Correct 6 ms 23388 KB Output is correct
6 Correct 6 ms 23644 KB Output is correct
7 Correct 6 ms 23684 KB Output is correct
8 Correct 8 ms 23900 KB Output is correct
9 Correct 6 ms 23616 KB Output is correct
10 Correct 6 ms 23640 KB Output is correct
11 Correct 6 ms 23684 KB Output is correct
12 Correct 7 ms 23640 KB Output is correct
13 Correct 6 ms 24152 KB Output is correct
14 Correct 6 ms 24156 KB Output is correct
15 Correct 6 ms 24416 KB Output is correct
16 Correct 6 ms 24156 KB Output is correct
17 Correct 6 ms 24400 KB Output is correct
18 Correct 7 ms 23896 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 23384 KB Output is correct
2 Correct 7 ms 23388 KB Output is correct
3 Correct 5 ms 23644 KB Output is correct
4 Correct 8 ms 23388 KB Output is correct
5 Correct 6 ms 23388 KB Output is correct
6 Correct 6 ms 23644 KB Output is correct
7 Correct 6 ms 23684 KB Output is correct
8 Correct 8 ms 23900 KB Output is correct
9 Correct 6 ms 23616 KB Output is correct
10 Correct 6 ms 23640 KB Output is correct
11 Correct 6 ms 23684 KB Output is correct
12 Correct 7 ms 23640 KB Output is correct
13 Correct 6 ms 24152 KB Output is correct
14 Correct 6 ms 24156 KB Output is correct
15 Correct 6 ms 24416 KB Output is correct
16 Correct 6 ms 24156 KB Output is correct
17 Correct 6 ms 24400 KB Output is correct
18 Correct 7 ms 23896 KB Output is correct
19 Correct 66 ms 125636 KB Output is correct
20 Correct 62 ms 121180 KB Output is correct
21 Correct 66 ms 135520 KB Output is correct
22 Correct 39 ms 55384 KB Output is correct
23 Runtime error 2230 ms 1048576 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23644 KB Output is correct
2 Correct 6 ms 23612 KB Output is correct
3 Correct 9 ms 23644 KB Output is correct
4 Correct 39 ms 23648 KB Output is correct
5 Correct 175 ms 24576 KB Output is correct
6 Correct 6 ms 23384 KB Output is correct
7 Correct 9 ms 31584 KB Output is correct
8 Correct 10 ms 31588 KB Output is correct
9 Correct 13 ms 31588 KB Output is correct
10 Correct 45 ms 31832 KB Output is correct
11 Correct 187 ms 32860 KB Output is correct
12 Correct 288 ms 811356 KB Output is correct
13 Correct 278 ms 811100 KB Output is correct
14 Correct 282 ms 811356 KB Output is correct
15 Correct 321 ms 811600 KB Output is correct
16 Correct 493 ms 812624 KB Output is correct
17 Runtime error 819 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 173396 KB Output is correct
2 Correct 108 ms 173388 KB Output is correct
3 Correct 223 ms 174164 KB Output is correct
4 Correct 371 ms 174676 KB Output is correct
5 Runtime error 363 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 23384 KB Output is correct
2 Correct 7 ms 23388 KB Output is correct
3 Correct 5 ms 23644 KB Output is correct
4 Correct 8 ms 23388 KB Output is correct
5 Correct 6 ms 23388 KB Output is correct
6 Correct 6 ms 23644 KB Output is correct
7 Correct 6 ms 23684 KB Output is correct
8 Correct 8 ms 23900 KB Output is correct
9 Correct 6 ms 23616 KB Output is correct
10 Correct 6 ms 23640 KB Output is correct
11 Correct 6 ms 23684 KB Output is correct
12 Correct 7 ms 23640 KB Output is correct
13 Correct 6 ms 24152 KB Output is correct
14 Correct 6 ms 24156 KB Output is correct
15 Correct 6 ms 24416 KB Output is correct
16 Correct 6 ms 24156 KB Output is correct
17 Correct 6 ms 24400 KB Output is correct
18 Correct 7 ms 23896 KB Output is correct
19 Correct 66 ms 125636 KB Output is correct
20 Correct 62 ms 121180 KB Output is correct
21 Correct 66 ms 135520 KB Output is correct
22 Correct 39 ms 55384 KB Output is correct
23 Runtime error 2230 ms 1048576 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -