제출 #954180

#제출 시각아이디문제언어결과실행 시간메모리
954180LucaIlieDynamic Diameter (CEOI19_diameter)C++17
11 / 100
2230 ms1048576 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; 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; }

컴파일 시 표준 에러 (stderr) 메시지

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;
      |                 ^
#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...