제출 #954130

#제출 시각아이디문제언어결과실행 시간메모리
954130LucaIlieDynamic Diameter (CEOI19_diameter)C++17
49 / 100
4889 ms223152 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...