#include<bits/stdc++.h>
using namespace std;
#define int long long
#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))
template<class T> bool minimize(T& a, T b){
if(a > b) return a = b, true;
return false;
}
template<class T> bool maximize(T& a, T b){
if(a < b) return a = b, true;
return false;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N = 1e5 + 5;
int n, m, q, timerDFS, lift[20][N], h[N], s[N], t[N], uNodes[N], vNodes[N], w[N], x[N], tin[N], tout[N], L[N], R[N], res[N], lca[N];
ll y[N];
pair<int, int> a[N];
vector<int> g[N];
void dfs(int u, int e){
tin[u] = ++timerDFS;
//cout << u << " : " << tin[u] << '\n';
for(int id : g[u]){
int v = uNodes[id] ^ vNodes[id] ^ u;
if(v != e){
h[v] = h[u] + 1;
lift[0][v] = u;
for(int i = 1; i <= 17; ++i){
lift[i][v] = lift[i - 1][lift[i - 1][v]];
}
dfs(v, u);
}
}
tout[u] = ++timerDFS;
}
int getLCA(int u, int v){
if(h[u] != h[v]){
for(int i = 17; i >= 0; --i){
if(h[u] - (1 << i) >= h[v]){
u = lift[i][u];
}
}
}
if(u == v) return u;
for(int i = 17; i >= 0; --i){
if(lift[i][u] != lift[i][v]){
u = lift[i][u];
v = lift[i][u];
}
}
return lift[0][u];
}
struct fenwickPath{
vector<ll> bit;
fenwickPath(int n) : bit(2 * n + 1, 0) {}
void update(int i, ll v){
for(; i < (int)bit.size(); i += i & (-i)){
bit[i] += v;
}
}
ll query(int i){
ll s = 0;
for(; i > 0; i -= i & (-i)){
s += bit[i];
}
return s;
}
void resetData(){
fill(range(bit), 0LL);
}
} goldPath(0), silverPath(0);
void add(bool type, int id, int sign){
int u = a[id].second;
if(!type){ //silver
silverPath.update(tin[u], a[id].first * sign);
silverPath.update(tout[u], -a[id].first * sign);
}
else{ //gold
goldPath.update(tin[u], 1 * sign);
goldPath.update(tout[u], -1 * sign);
}
}
ll queryPath(bool type, int i){
if(!type) {
return silverPath.query(tin[s[i]]) + silverPath.query(tin[t[i]]) - 2LL * silverPath.query(tin[lca[i]]);
}
else{
return goldPath.query(tin[s[i]]) + goldPath.query(tin[t[i]]) - 2LL * goldPath.query(tin[lca[i]]);
}
}
void Zero_OP(){
cin >> n >> m >> q;
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
g[u].push_back(i);
g[v].push_back(i);
uNodes[i] = u, vNodes[i] = v;
}
dfs(1, 1);
for(int i = 1; i <= m; ++i){
int p, c;
cin >> p >> c;
if(tin[uNodes[p]] < tin[vNodes[p]]) p = vNodes[p];
else p = uNodes[p];
a[i] = {c, p};
}
sort(a + 1, a + 1 + m);
for(int i = 1; i <= q; ++i){
cin >> s[i] >> t[i] >> x[i] >> y[i];
lca[i] = getLCA(s[i], t[i]), L[i] = 0, R[i] = m, res[i] = -1;
}
silverPath = fenwickPath(n), goldPath = fenwickPath(n);
int timesTotsBS = 20; //maybe should be 17 18
while(timesTotsBS--){
vector<pair<int, int>> events;
for(int i = 1; i <= q; ++i){
if(L[i] <= R[i]){
// cout << i << " : " << (L[i] + R[i] >> 1) << '\n';
events.push_back({L[i] + R[i] >> 1, i});
}
}
if(events.empty()) break;
sort(range(events));
int ptr = 1;
for(int i = 1; i <= m; ++i){
add(1, i, 1);
}
for(int i = 0; i < events.size(); ++i){
while(ptr <= m and ptr <= events[i].first){
add(1, ptr, -1);
add(0, ptr, 1);
++ptr;
}
int mid = events[i].first, id = events[i].second;
ll curSilver = queryPath(0, id), curGold = queryPath(1, id);
assert(curGold >= 0);
//cout << id << ' ' << mid << ' ' << curSilver << ' ' << curGold << '\n';
if(curSilver <= y[id] and curGold <= x[id]){
res[id] = x[id] - curGold;
// cout << id << ' ' << x[id] << ' ' << curGold << '\n';
L[id] = mid + 1;
}
else{
R[id] = mid - 1;
}
}
silverPath.resetData();
goldPath.resetData();
}
for(int i = 1; i <= q; ++i){
cout << res[i] << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen("antuvu.inp", "r")){
freopen("antuvu.inp", "r", stdin);
// freopen("antuvu.out", "w", stdout);
}
Zero_OP();
return 0;
}
Compilation message
currencies.cpp: In function 'void Zero_OP()':
currencies.cpp:150:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
150 | events.push_back({L[i] + R[i] >> 1, i});
| ~~~~~^~~~~~
currencies.cpp:163:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i = 0; i < events.size(); ++i){
| ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:200:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
200 | freopen("antuvu.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
3 ms |
27228 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
27228 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
27388 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
27484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
27224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
3 ms |
27228 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
27228 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
