#include <bits/stdc++.h>
#define int long long
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, y;
};
struct operation {
char type;
int val, u, v, q;
};
struct answer {
int sum, cnt;
};
struct AIB {
vector<int> 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;
}
};
const int MAX_N = 1e5;
const int MAX_M = 1e5;
const int MAX_Q = 1e5;
const int MAX_C = 1e9;
const int MAX_LOG_C = 30;
const int MAX_LOG_N = 16;
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];
query queries[MAX_Q];
vector<operation> operations;
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 = 0; 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] )
};
}
signed main() {
int q;
cin >> n >> m >> q;
for ( int i = 1; i < n; i++ )
cin >> edges[i].u >> edges[i].v;
for ( int i = 0; i < m; i++ )
cin >> checkpoints[i].e >> checkpoints[i].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] = MAX_C;
}
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_C + 1; pas++ ) {
operations.clear();
for ( int i = 0; i < m; i++ )
operations.push_back( { 'u', checkpoints[i].c, 0, edges[checkpoints[i].e].v, 0 } );
for ( int i = 0; i < q; i++ )
operations.push_back( { 'q', (leftBS[i] + rightBS[i]) / 2, queries[i].u, queries[i].v, i } );
sort( operations.begin(), operations.end(), []( operation a, operation b ) {
if ( a.val == b.val )
return (a.type == 'u');
return a.val < b.val;
} );
initArb();
for ( operation o: operations ) {
if ( o.type == 'u' )
updateArb( o.v, o.val );
else {
auto x = queryArb( o.u, o.v );
if ( x.sum > queries[o.q].y )
rightBS[o.q] = o.val;
else
leftBS[o.q] = o.val;
ans[o.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
currencies.cpp: In member function 'void AIB::init(long long int)':
currencies.cpp:37:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for ( int i = 0; i < aib.size(); i++ )
| ~~^~~~~~~~~~~~
currencies.cpp: In member function 'void AIB::update(long long int, long long int)':
currencies.cpp:42:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | while ( i < aib.size() ) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2772 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
27 ms |
3796 KB |
Output is correct |
| 3 |
Correct |
28 ms |
3772 KB |
Output is correct |
| 4 |
Correct |
28 ms |
3796 KB |
Output is correct |
| 5 |
Correct |
3267 ms |
43840 KB |
Output is correct |
| 6 |
Correct |
3351 ms |
42628 KB |
Output is correct |
| 7 |
Correct |
2945 ms |
38096 KB |
Output is correct |
| 8 |
Execution timed out |
5100 ms |
51608 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2772 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
