#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,Q,dub[100005],rod[20][100005],in[100005],out[100005],vrem=0;
struct grana{
int c1,c2;
} grane[100005];
struct stan{
ll gde,cena;
} stanica[100005];
bool cmp(stan a,stan b){
return a.cena<b.cena;
}
struct upit{
ll novca,zlato;
int dg,gg,res,a,b;
} upiti[100005];
vector<int> stablo[100005],bucket[100005];
void dfs(int gde,int pret){
rod[0][gde]=pret;
in[gde]=++vrem;
dub[gde]=dub[pret]+1;
for(int i=0;i<stablo[gde].size();i++){
if(stablo[gde][i]==pret)
continue;
dfs(stablo[gde][i],gde);
}
out[gde]=vrem;
return;
}
ll flosih[100005],fcena[100005];
void lupdate(int gde,ll kol){
for(int i=gde;i<=N;i+=(i)&(-i))
flosih[i]+=kol;
return;
}
void cupdate(int gde,ll kol){
for(int i=gde;i<=N;i+=(i)&(-i))
fcena[i]+=kol;
return;
}
ll lget(int gde){
ll ret=0;
for(int i=gde;i>=1;i-=(i)&(-i))
ret+=flosih[i];
return ret;
}
ll cget(int gde){
ll ret=0;
for(int i=gde;i>=1;i-=(i)&(-i))
ret+=fcena[i];
return ret;
}
void aktiviraj(int koga){
int a=in[stanica[koga].gde];
int b=out[stanica[koga].gde];
lupdate(a,-1);
lupdate(b+1,1);
cupdate(a,stanica[koga].cena);
cupdate(b+1,-stanica[koga].cena);
return;
}
bool isparent(int a,int b){
return in[a]<=in[b] and out[a]>=out[b];
}
int LCA(int a,int b){
if(isparent(a,b))
return a;
if(isparent(b,a))
return b;
for(int i=17;i>=0;i--)
if(!isparent(rod[i][a],b))
a=rod[i][a];
return rod[0][a];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>M>>Q;
for(int i=1;i<N;i++){
cin>>grane[i].c1>>grane[i].c2;
stablo[grane[i].c1].push_back(grane[i].c2);
stablo[grane[i].c2].push_back(grane[i].c1);
}
dfs(1,1);
for(int j=1;j<=18;j++)
for(int i=1;i<=N;i++)
rod[j][i]=rod[j-1][rod[j-1][i]];
for(int i=1;i<=M;i++){
cin>>stanica[i].gde>>stanica[i].cena;
int a=grane[stanica[i].gde].c1;
int b=grane[stanica[i].gde].c2;
if(dub[a]>dub[b])
stanica[i].gde=a;
else
stanica[i].gde=b;
}
sort(stanica+1,stanica+1+M,cmp);
for(int i=1;i<=Q;i++){
cin>>upiti[i].a>>upiti[i].b>>upiti[i].zlato>>upiti[i].novca;
upiti[i].dg=0;
upiti[i].gg=M;
}
bool nastavi=true;
while(nastavi){
nastavi=false;
for(int i=1;i<=Q;i++){
if(upiti[i].gg<upiti[i].dg)
continue;
// cout<<upiti[i].dg<<" "<<upiti[i].gg<<endl;
nastavi=true;
bucket[(upiti[i].dg+upiti[i].gg)/2].push_back(i);
}
if(!nastavi)
break;
for(int i=1;i<=N;i++){
flosih[i]=0;
fcena[i]=0;
}
for(int i=1;i<=M;i++){
int a=in[stanica[i].gde];
int b=out[stanica[i].gde];
lupdate(a,1);
lupdate(b+1,-1);
}
for(int sred=0;sred<=M;sred++){
if(sred!=0)
aktiviraj(sred);
for(int i=0;i<bucket[sred].size();i++){
int koji=bucket[sred][i];
int lc=LCA(upiti[koji].a,upiti[koji].b);
ll c=cget(in[upiti[koji].a])+cget(in[upiti[koji].b])-2*cget(in[lc]);
ll z=lget(in[upiti[koji].a])+lget(in[upiti[koji].b])-2*lget(in[lc]);
// cout<<c<<" "<<z<<endl;
if(c<=upiti[koji].novca){
upiti[koji].res=z;
upiti[koji].dg=sred+1;
}
else
upiti[koji].gg=sred-1;
}
bucket[sred].clear();
}
}
for(int i=1;i<=Q;i++){
if(upiti[i].zlato<upiti[i].res)
cout<<"-1\n";
else
cout<<upiti[i].zlato-upiti[i].res<<"\n";
}
return 0;
}
/*
8 7 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
*/
Compilation message
currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0;i<stablo[gde].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i=0;i<bucket[sred].size();i++){
| ~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5076 KB |
Output is correct |
5 |
Correct |
11 ms |
5588 KB |
Output is correct |
6 |
Correct |
12 ms |
5672 KB |
Output is correct |
7 |
Correct |
10 ms |
5608 KB |
Output is correct |
8 |
Correct |
12 ms |
5764 KB |
Output is correct |
9 |
Correct |
13 ms |
5716 KB |
Output is correct |
10 |
Correct |
13 ms |
5844 KB |
Output is correct |
11 |
Correct |
13 ms |
5672 KB |
Output is correct |
12 |
Correct |
13 ms |
5728 KB |
Output is correct |
13 |
Correct |
10 ms |
5844 KB |
Output is correct |
14 |
Correct |
11 ms |
5972 KB |
Output is correct |
15 |
Correct |
12 ms |
5844 KB |
Output is correct |
16 |
Correct |
12 ms |
5752 KB |
Output is correct |
17 |
Correct |
13 ms |
5716 KB |
Output is correct |
18 |
Correct |
12 ms |
5716 KB |
Output is correct |
19 |
Correct |
11 ms |
5712 KB |
Output is correct |
20 |
Correct |
11 ms |
5736 KB |
Output is correct |
21 |
Correct |
11 ms |
5732 KB |
Output is correct |
22 |
Correct |
11 ms |
5836 KB |
Output is correct |
23 |
Correct |
11 ms |
5752 KB |
Output is correct |
24 |
Correct |
11 ms |
5716 KB |
Output is correct |
25 |
Correct |
15 ms |
5692 KB |
Output is correct |
26 |
Correct |
11 ms |
5696 KB |
Output is correct |
27 |
Correct |
10 ms |
5692 KB |
Output is correct |
28 |
Correct |
11 ms |
5748 KB |
Output is correct |
29 |
Correct |
10 ms |
5736 KB |
Output is correct |
30 |
Correct |
12 ms |
5716 KB |
Output is correct |
31 |
Correct |
13 ms |
5716 KB |
Output is correct |
32 |
Correct |
12 ms |
5704 KB |
Output is correct |
33 |
Correct |
8 ms |
5876 KB |
Output is correct |
34 |
Correct |
8 ms |
5908 KB |
Output is correct |
35 |
Correct |
8 ms |
5868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
12 ms |
5716 KB |
Output is correct |
3 |
Correct |
13 ms |
5732 KB |
Output is correct |
4 |
Correct |
13 ms |
5744 KB |
Output is correct |
5 |
Correct |
1674 ms |
33484 KB |
Output is correct |
6 |
Correct |
1876 ms |
33996 KB |
Output is correct |
7 |
Correct |
1966 ms |
34632 KB |
Output is correct |
8 |
Correct |
1332 ms |
31152 KB |
Output is correct |
9 |
Correct |
1461 ms |
30824 KB |
Output is correct |
10 |
Correct |
3178 ms |
39888 KB |
Output is correct |
11 |
Correct |
2929 ms |
39892 KB |
Output is correct |
12 |
Correct |
2596 ms |
39904 KB |
Output is correct |
13 |
Correct |
2541 ms |
40012 KB |
Output is correct |
14 |
Correct |
2405 ms |
40280 KB |
Output is correct |
15 |
Correct |
1118 ms |
46512 KB |
Output is correct |
16 |
Correct |
821 ms |
46896 KB |
Output is correct |
17 |
Correct |
1053 ms |
46124 KB |
Output is correct |
18 |
Correct |
2833 ms |
40456 KB |
Output is correct |
19 |
Correct |
2612 ms |
40436 KB |
Output is correct |
20 |
Correct |
2819 ms |
40396 KB |
Output is correct |
21 |
Correct |
2809 ms |
39932 KB |
Output is correct |
22 |
Correct |
2577 ms |
40256 KB |
Output is correct |
23 |
Correct |
2542 ms |
40320 KB |
Output is correct |
24 |
Correct |
2314 ms |
40228 KB |
Output is correct |
25 |
Correct |
1852 ms |
40648 KB |
Output is correct |
26 |
Correct |
1535 ms |
40260 KB |
Output is correct |
27 |
Correct |
1594 ms |
40780 KB |
Output is correct |
28 |
Correct |
749 ms |
38688 KB |
Output is correct |
29 |
Correct |
662 ms |
37788 KB |
Output is correct |
30 |
Correct |
930 ms |
38304 KB |
Output is correct |
31 |
Correct |
899 ms |
38352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5076 KB |
Output is correct |
2 |
Correct |
9 ms |
5868 KB |
Output is correct |
3 |
Correct |
9 ms |
5864 KB |
Output is correct |
4 |
Correct |
8 ms |
5844 KB |
Output is correct |
5 |
Correct |
347 ms |
38808 KB |
Output is correct |
6 |
Correct |
326 ms |
38104 KB |
Output is correct |
7 |
Correct |
517 ms |
34812 KB |
Output is correct |
8 |
Correct |
640 ms |
46984 KB |
Output is correct |
9 |
Correct |
660 ms |
46996 KB |
Output is correct |
10 |
Correct |
580 ms |
47064 KB |
Output is correct |
11 |
Correct |
507 ms |
47152 KB |
Output is correct |
12 |
Correct |
530 ms |
47020 KB |
Output is correct |
13 |
Correct |
504 ms |
47004 KB |
Output is correct |
14 |
Correct |
476 ms |
46496 KB |
Output is correct |
15 |
Correct |
421 ms |
46084 KB |
Output is correct |
16 |
Correct |
497 ms |
46720 KB |
Output is correct |
17 |
Correct |
496 ms |
46740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5076 KB |
Output is correct |
5 |
Correct |
11 ms |
5588 KB |
Output is correct |
6 |
Correct |
12 ms |
5672 KB |
Output is correct |
7 |
Correct |
10 ms |
5608 KB |
Output is correct |
8 |
Correct |
12 ms |
5764 KB |
Output is correct |
9 |
Correct |
13 ms |
5716 KB |
Output is correct |
10 |
Correct |
13 ms |
5844 KB |
Output is correct |
11 |
Correct |
13 ms |
5672 KB |
Output is correct |
12 |
Correct |
13 ms |
5728 KB |
Output is correct |
13 |
Correct |
10 ms |
5844 KB |
Output is correct |
14 |
Correct |
11 ms |
5972 KB |
Output is correct |
15 |
Correct |
12 ms |
5844 KB |
Output is correct |
16 |
Correct |
12 ms |
5752 KB |
Output is correct |
17 |
Correct |
13 ms |
5716 KB |
Output is correct |
18 |
Correct |
12 ms |
5716 KB |
Output is correct |
19 |
Correct |
11 ms |
5712 KB |
Output is correct |
20 |
Correct |
11 ms |
5736 KB |
Output is correct |
21 |
Correct |
11 ms |
5732 KB |
Output is correct |
22 |
Correct |
11 ms |
5836 KB |
Output is correct |
23 |
Correct |
11 ms |
5752 KB |
Output is correct |
24 |
Correct |
11 ms |
5716 KB |
Output is correct |
25 |
Correct |
15 ms |
5692 KB |
Output is correct |
26 |
Correct |
11 ms |
5696 KB |
Output is correct |
27 |
Correct |
10 ms |
5692 KB |
Output is correct |
28 |
Correct |
11 ms |
5748 KB |
Output is correct |
29 |
Correct |
10 ms |
5736 KB |
Output is correct |
30 |
Correct |
12 ms |
5716 KB |
Output is correct |
31 |
Correct |
13 ms |
5716 KB |
Output is correct |
32 |
Correct |
12 ms |
5704 KB |
Output is correct |
33 |
Correct |
8 ms |
5876 KB |
Output is correct |
34 |
Correct |
8 ms |
5908 KB |
Output is correct |
35 |
Correct |
8 ms |
5868 KB |
Output is correct |
36 |
Correct |
3 ms |
5076 KB |
Output is correct |
37 |
Correct |
12 ms |
5716 KB |
Output is correct |
38 |
Correct |
13 ms |
5732 KB |
Output is correct |
39 |
Correct |
13 ms |
5744 KB |
Output is correct |
40 |
Correct |
1674 ms |
33484 KB |
Output is correct |
41 |
Correct |
1876 ms |
33996 KB |
Output is correct |
42 |
Correct |
1966 ms |
34632 KB |
Output is correct |
43 |
Correct |
1332 ms |
31152 KB |
Output is correct |
44 |
Correct |
1461 ms |
30824 KB |
Output is correct |
45 |
Correct |
3178 ms |
39888 KB |
Output is correct |
46 |
Correct |
2929 ms |
39892 KB |
Output is correct |
47 |
Correct |
2596 ms |
39904 KB |
Output is correct |
48 |
Correct |
2541 ms |
40012 KB |
Output is correct |
49 |
Correct |
2405 ms |
40280 KB |
Output is correct |
50 |
Correct |
1118 ms |
46512 KB |
Output is correct |
51 |
Correct |
821 ms |
46896 KB |
Output is correct |
52 |
Correct |
1053 ms |
46124 KB |
Output is correct |
53 |
Correct |
2833 ms |
40456 KB |
Output is correct |
54 |
Correct |
2612 ms |
40436 KB |
Output is correct |
55 |
Correct |
2819 ms |
40396 KB |
Output is correct |
56 |
Correct |
2809 ms |
39932 KB |
Output is correct |
57 |
Correct |
2577 ms |
40256 KB |
Output is correct |
58 |
Correct |
2542 ms |
40320 KB |
Output is correct |
59 |
Correct |
2314 ms |
40228 KB |
Output is correct |
60 |
Correct |
1852 ms |
40648 KB |
Output is correct |
61 |
Correct |
1535 ms |
40260 KB |
Output is correct |
62 |
Correct |
1594 ms |
40780 KB |
Output is correct |
63 |
Correct |
749 ms |
38688 KB |
Output is correct |
64 |
Correct |
662 ms |
37788 KB |
Output is correct |
65 |
Correct |
930 ms |
38304 KB |
Output is correct |
66 |
Correct |
899 ms |
38352 KB |
Output is correct |
67 |
Correct |
2 ms |
5076 KB |
Output is correct |
68 |
Correct |
9 ms |
5868 KB |
Output is correct |
69 |
Correct |
9 ms |
5864 KB |
Output is correct |
70 |
Correct |
8 ms |
5844 KB |
Output is correct |
71 |
Correct |
347 ms |
38808 KB |
Output is correct |
72 |
Correct |
326 ms |
38104 KB |
Output is correct |
73 |
Correct |
517 ms |
34812 KB |
Output is correct |
74 |
Correct |
640 ms |
46984 KB |
Output is correct |
75 |
Correct |
660 ms |
46996 KB |
Output is correct |
76 |
Correct |
580 ms |
47064 KB |
Output is correct |
77 |
Correct |
507 ms |
47152 KB |
Output is correct |
78 |
Correct |
530 ms |
47020 KB |
Output is correct |
79 |
Correct |
504 ms |
47004 KB |
Output is correct |
80 |
Correct |
476 ms |
46496 KB |
Output is correct |
81 |
Correct |
421 ms |
46084 KB |
Output is correct |
82 |
Correct |
497 ms |
46720 KB |
Output is correct |
83 |
Correct |
496 ms |
46740 KB |
Output is correct |
84 |
Correct |
1394 ms |
31636 KB |
Output is correct |
85 |
Correct |
1155 ms |
28692 KB |
Output is correct |
86 |
Correct |
1109 ms |
27620 KB |
Output is correct |
87 |
Correct |
2669 ms |
39936 KB |
Output is correct |
88 |
Correct |
2552 ms |
39360 KB |
Output is correct |
89 |
Correct |
2363 ms |
39916 KB |
Output is correct |
90 |
Correct |
2496 ms |
39972 KB |
Output is correct |
91 |
Correct |
2461 ms |
39992 KB |
Output is correct |
92 |
Correct |
1222 ms |
44620 KB |
Output is correct |
93 |
Correct |
1111 ms |
45964 KB |
Output is correct |
94 |
Correct |
2212 ms |
40516 KB |
Output is correct |
95 |
Correct |
2160 ms |
40436 KB |
Output is correct |
96 |
Correct |
2270 ms |
40236 KB |
Output is correct |
97 |
Correct |
2356 ms |
40568 KB |
Output is correct |
98 |
Correct |
2280 ms |
40280 KB |
Output is correct |
99 |
Correct |
2324 ms |
40028 KB |
Output is correct |
100 |
Correct |
2516 ms |
39848 KB |
Output is correct |
101 |
Correct |
2543 ms |
40440 KB |
Output is correct |
102 |
Correct |
1695 ms |
40616 KB |
Output is correct |
103 |
Correct |
1844 ms |
40564 KB |
Output is correct |
104 |
Correct |
1826 ms |
40572 KB |
Output is correct |
105 |
Correct |
747 ms |
37732 KB |
Output is correct |
106 |
Correct |
770 ms |
38180 KB |
Output is correct |
107 |
Correct |
1169 ms |
37708 KB |
Output is correct |
108 |
Correct |
976 ms |
37912 KB |
Output is correct |