Submission #837035

#TimeUsernameProblemLanguageResultExecution timeMemory
837035LucaIlieTwo Currencies (JOI23_currencies)C++17
0 / 100
20 ms15476 KiB
#include <bits/stdc++.h> using namespace std; struct edge { int u, v; int other( int x ) { return u ^ v ^ x; } }; struct checkpoint { int e, c; }; struct query { int u, v, x; long long y; }; struct answer { int sum, cnt; }; struct AIB { vector<long long> aib; void init( int n ) { aib.resize( n + 1 ); for ( int i = 0; i < aib.size(); i++ ) aib[i] = 0; } void update( int i, int x ) { while ( i < aib.size() ) { aib[i] += x; i += (i & -i); } } int query( int i ) { int s = 0; while ( i > 0 ) { s += aib[i]; i -= (i & -i); } return s; } }; struct updateBS { int v, val; }; struct queryBS { int u, v, q; }; const int MAX_N = 2e5; const int MAX_M = 2e5; const int MAX_Q = 2e5; const int MAX_LOG_N = 17; int n, m; int leftBS[MAX_Q], rightBS[MAX_Q], ans[MAX_Q]; int depth[MAX_N + 1], leftPos[MAX_N + 1], rightPos[MAX_N + 1], parent[MAX_LOG_N + 1][MAX_N + 1]; edge edges[MAX_N]; checkpoint checkpoints[MAX_M + 1]; query queries[MAX_Q]; vector<updateBS> updatesBS[MAX_M + 2]; vector<queryBS> queriesBS[MAX_M + 2]; vector<int> adj[MAX_N + 1]; AIB sum, cnt; int timee = 0; void dfs( int u, int p ) { parent[0][u] = p; depth[u] = depth[p] + 1; leftPos[u] = ++timee; for ( int e: adj[u] ) { int v = edges[e].other( u ); if ( v == p ) continue; dfs( v, u ); if ( u != edges[e].u ) swap( edges[e].u, edges[e].v ); } rightPos[u] = timee; } int lca( int u, int v ) { if ( depth[u] < depth[v] ) swap( u, v ); for ( int l = MAX_LOG_N; l >= 0; l-- ) { if ( depth[parent[l][u]] >= depth[v] ) u = parent[l][u]; } if ( u == v ) return u; for ( int l = MAX_LOG_N; l >= 0; l-- ) { if ( parent[l][u] != parent[l][v] ) { u = parent[l][u]; v = parent[l][v]; } } return parent[0][u]; } void initArb() { sum.init( n ); cnt.init( n ); for ( int i = 1; i <= m; i++ ) { int u = edges[checkpoints[i].e].v; cnt.update( leftPos[u], 1 ); cnt.update( rightPos[u] + 1, -1 ); } } void updateArb( int u, int val ) { sum.update( leftPos[u], val ); sum.update( rightPos[u] + 1, -val ); cnt.update( leftPos[u], -1 ); cnt.update( rightPos[u] + 1, 1 ); } answer queryArb( int u, int v ) { int l = lca( u, v ); return { sum.query( leftPos[u] ) + sum.query( leftPos[v] ) - 2 * sum.query( leftPos[l] ), cnt.query( leftPos[u] ) + cnt.query( leftPos[v] ) - 2 * cnt.query( leftPos[l] ) }; } int main() { cin.tie( NULL ); cout.tie( NULL ); ios_base::sync_with_stdio( false ); int q; cin >> n >> m >> q; for ( int i = 1; i < n; i++ ) cin >> edges[i].u >> edges[i].v; for ( int i = 1; i <= m; i++ ) cin >> checkpoints[i].e >> checkpoints[i].c; sort( checkpoints + 1, checkpoints + 1 + m, []( checkpoint a, checkpoint b ) { return a.c < b.c; } ); for ( int i = 0; i < q; i++ ) { cin >> queries[i].u >> queries[i].v >> queries[i].x >> queries[i].y; leftBS[i] = 0; rightBS[i] = m + 2; } for ( int i = 1; i < n; i++ ) { adj[edges[i].u].push_back( i ); adj[edges[i].v].push_back( i ); } dfs( 1, 0 ); for ( int l = 1; l <= MAX_LOG_N; l++ ) { for ( int u = 1; u <= n; u++ ) parent[l][u] = parent[l - 1][parent[l - 1][u]]; } for ( int pas = 0; pas < MAX_LOG_N + 1; pas++ ) { for ( int i = 0; i <= m + 1; i++ ) { updatesBS[i].clear(); queriesBS[i].clear(); } for ( int i = 1; i <= m; i++ ) updatesBS[i].push_back( { edges[checkpoints[i].e].v, checkpoints[i].c } ); for ( int i = 0; i < q; i++ ) queriesBS[(leftBS[i] + rightBS[i]) / 2].push_back( { queries[i].u, queries[i].v, i } ); initArb(); for ( int i = 0; i <= m + 1; i++ ) { for ( updateBS u: updatesBS[i] ) updateArb( u.v, u.val ); for ( queryBS qq: queriesBS[i] ) { answer x = queryArb( qq.u, qq.v ); if ( x.sum > queries[qq.q].y ) rightBS[qq.q] = i; else leftBS[qq.q] = i; ans[qq.q] = x.cnt; } } } for ( int i = 0; i < q; i++ ) cout << (ans[i] <= queries[i].x ? queries[i].x - ans[i] : -1) << "\n"; return 0; }

Compilation message (stderr)

currencies.cpp: In member function 'void AIB::init(int)':
currencies.cpp:31:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for ( int i = 0; i < aib.size(); i++ )
      |                          ~~^~~~~~~~~~~~
currencies.cpp: In member function 'void AIB::update(int, int)':
currencies.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...