//####################
//TwoCurrencies
//####################
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxiN = 1000000;
const int LOG = 17;
vector < int > links[maxiN];
int depth[maxiN];
int up[maxiN][LOG];
void root(int node, int d = 0, int parent = -1) {
up[node][0] = parent;
depth[node] = d;
for (int v: links[node])
if (v != parent) {
root(v, d + 1, node);
}
}
int getK(int node, int K) {
for (int i = LOG - 1; i >= 0; i--) {
if ((K >> i) & 1) {
node = up[node][i];
}
}
return node;
}
int LCA(int a, int b) {
if (depth[b] > depth[a]) swap(a, b);
a = getK(a, depth[a] - depth[b]);
if (a == b) {
return a;
}
for (int l = LOG - 1; l >= 0; l--) {
if (up[a][l] != up[b][l]) {
a = up[a][l];
b = up[b][l];
}
}
return up[a][0];
}
map < int, vector < int >> peages;
vector < int > val[maxiN];
pair<int,int> eulerseg[maxiN];
int actEuleur=-1;
void computeEuleurTour(int node,int parent = -1){
actEuleur++;
eulerseg[node].first = actEuleur;
for(int v:links[node])if(parent!=v){
computeEuleurTour(v,node);
}
actEuleur++;
eulerseg[node].second = actEuleur;
}
struct segtree{
vector<int> vals;
int leaf;
segtree(int n){
leaf = (1<<((int)ceil(log2(n))));
vals.resize(2*leaf);
fill(vals.begin(),vals.end(),0);
}
void _addRange(int a,int b,int val){
if(a==b){
vals[a]+=val;
}else if(a&1){
vals[a]+=val;
_addRange(a+1,b,val);
}else if(b%2==0){
vals[b]+=val;
_addRange(a,b-1,val);
}else{
_addRange(a/2,b/2,val);
}
}
void addRange(int a,int b,int val){
_addRange(a+leaf,b+leaf,val);
}
int getVal(int pos){
pos+=leaf;
int re = 0;
for(int p=pos;p>=1;p>>=1){
re+=vals[p];
}
return re;
}
};
signed main() {
fill(depth, depth + maxiN, -1);
int n, m, q;
cin >> n >> m >> q;
segtree counter(3*n);
vector < pair < int, int >> edges;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
edges.push_back(make_pair(a, b));
links[a].push_back(b);
links[b].push_back(a);
}
root(0, 0, -1);
int C;
for (int i = 0; i < m; i++) {
int p, c;
cin >> p >> c;
C = c;
p--;
auto a = edges[p].first;
auto b = edges[p].second;
if (depth[a] < depth[b]) swap(a, b);
peages[c].push_back(a);
val[a].push_back(c);
}
//On calcule la tab de LCA
for (int l = 1; l < LOG; l++) {
for (int i = 0; i < n; i++) {
if (up[i][l - 1] == -1) {
up[i][l] = -1;
}
up[i][l] = up[up[i][l - 1]][l - 1];
}
}
computeEuleurTour(0);
for(int i = 0;i<n;i++){
counter.addRange(eulerseg[i].first,eulerseg[i].second,val[i].size());
}
for (int i = 0; i < q; i++) {
int a, b, x, y;
cin >> a >> b >> x >> y;
a--;
b--;
int lca = LCA(a, b);
int ans = 0;
int nbocc = counter.getVal(a) + counter.getVal(b) - 2*counter.getVal(lca);
int nb_silver = y/C;
int g=0;
if(nb_silver>=nbocc){g=0;}
else{g=nbocc-nb_silver;}
if(g<=x){
cout<<x-g<<endl;
}else{
cout<<-1<<endl;
}
}
return 0;
};
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:140:17: warning: unused variable 'ans' [-Wunused-variable]
140 | int ans = 0;
| ^~~
currencies.cpp:142:17: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
142 | int nb_silver = y/C;
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
57948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
58084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
57944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
57948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
