#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int pa[100005][20];
int lv[100005];
long long ar[100005];
vector<long long>edcp[100005];
const int N=1e5;
pair<int,long long>cp[100005];
vector<int>v[100005];
pair<int,int>edge[100005];
map<pair<int,int>,int >mp;
struct persist{
struct node{
long long sum,freq;
node *l;
node *r;
node(long long v=0,long long f=0){
sum=v;
freq=f;
l=NULL;
r=NULL;
}
};
typedef node* pnode;
pnode rt[100005]={};
long long gsum(pnode x){
return x?x->sum:0;
}
int gfreq(pnode x){
return x?x->freq:0;
}
void build(int st,int en,pnode &x){
x=new node();
if(st==en){
return;
}
int m=(st+en)/2;
build(st,m,x->l);
build(m+1,en,x->r);
}
void build(){
build(1,N,rt[0]);
}
void upd(int st,int en,pnode &x,long long pos,long long val,pnode k){
if(k==NULL){
cout<<"NULL"<<endl;
}
x=new node(*k);
if(st==en){
x->sum+=val;
x->freq++;
return;
}
int m=(st+en)/2;
if(pos<=m){
upd(st,m,x->l,pos,val,k->l);
}else{
upd(m+1,en,x->r,pos,val,k->r);
}
x->sum=gsum(x->l)+gsum(x->r);
x->freq=gfreq(x->l)+gfreq(x->r);
}
void upd(int st,int en,long long pos,long long val,int check){
if(check==0){
rt[en]=new node(*rt[st]);
return;
}
if(rt[en]==NULL){
upd(1,N,rt[en],pos,val,rt[st]);
}else{
upd(1,N,rt[en],pos,val,rt[en]);
}
}
long long fans(int st,int en,pnode p,pnode x,pnode y,long long k){
//cout<<st<<" "<<en<<" "<<k<<":"<<endl;
if(st==en){
long long f=x->freq+y->freq-2*p->freq;
//cout<<st<<" "<<ar[st]<<endl;
if(f==0){
return 0;
}
long long id=ar[st];
long long ans=min(k/id,f);
return ans;
}
//cout<<"sum: "<<gsum(x->l)<<" "<<gsum(p->l)<<" "<<gsum(y->l)<<" "<<gsum(p->l)<<" "<<endl;
long long sum=gsum(x->l)-gsum(p->l)+gsum(y->l)-gsum(p->l);
long long freq=gfreq(x->l)-gfreq(p->l)+gfreq(y->l)-gfreq(p->l);
//cout<<"sum,freq:"<<sum<<" "<<freq<<endl;
int m=(st+en)/2;
if(k<=sum){
//cout<<"go left"<<endl;
return fans(st,m,p->l,x->l,y->l,k);
}else{
//cout<<"go right"<<endl;
return fans(m+1,en,p->r,x->r,y->r,k-sum)+freq;
}
}
long long fans(int p,int x,int y,long long k){
return fans(1,N,rt[p],rt[x],rt[y],k);
}
}pst;
void dfs(int i,int p){
//cout<<i<<" "<<p<<endl;
pa[i][0]=p;
lv[i]=lv[p]+1;
for(int j=1;j<20;j++){
pa[i][j]=pa[pa[i][j-1]][j-1];
}
int ednum=mp[{i,p}];
for(int j=0;j<edcp[ednum].size();j++){
long long b=edcp[ednum][j];
int num=lower_bound(ar,ar+m+1,b)-ar;
//cout<<"upd:"<<p<<" "<<i<<" "<<num<<" "<<b<<" "<<endl;
pst.upd(p,i,num,b,1);
}
if(edcp[ednum].size()==0){
//cout<<"upd:NO UPD"<<endl;
pst.upd(p,i,0,0,0);
}
/*int id=mp[{i,p}];
int b=cp[id].second;
int num=lower_bound(ar,ar+m+1,b)-ar;
cout<<"upd:"<<p<<" "<<i<<" "<<num<<" "<<b<<" "<<id<<endl;
pst.upd(p,i,num,b);*/
for(int j=0;j<v[i].size();j++){
if(v[i][j]!=p){
dfs(v[i][j],i);
}
}
}
int lca(int a,int b){
if(lv[b]>lv[a]){
swap(a,b);
}
for(int i=19;i>=0;i--){
if(lv[pa[a][i]]>=lv[b]){
a=pa[a][i];
}
}
if(a==b){
return a;
}
for(int i=19;i>=0;i--){
if(pa[a][i]!=pa[b][i]){
a=pa[a][i];
b=pa[b][i];
}
}
return pa[a][0];
}
int main(){
cin>>n>>m>>q;
pst.build();
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
edge[i].first=a;
edge[i].second=b;
mp[{a,b}]=i;
mp[{b,a}]=i;
}
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
cp[i]={a,b};
int ednum=a;
edcp[a].push_back(b);
ar[i]=b;
}
/*for(int i=0;i<=n;i++){
cout<<ar[i]<<" ";
}*/
cout<<endl;
sort(ar+1,ar+m+1);
pst.upd(0,1,1,0,0);
dfs(1,0);
//cout<<"work"<<endl;
for(int i=1;i<=q;i++){
long long a,b,c,d;
cin>>a>>b>>c>>d;
int x=lca(a,b);
int sz=pst.fans(x,a,b,LLONG_MAX);
//cout<<"SIZE IS "<<sz<<endl;
//cout<<"info"<<endl;
//cout<<x<<" "<<a<<" "<<b<<endl;
int use=pst.fans(x,a,b,d);
sz-=use;
c-=sz;
//cout<<"ANS::";
if(c<0){
cout<<"-1\n";
}else{
cout<<c<<"\n";
}
}
}
Compilation message
currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int j=0;j<edcp[ednum].size();j++){
| ~^~~~~~~~~~~~~~~~~~~
currencies.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int j=0;j<v[i].size();j++){
| ~^~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:170:13: warning: unused variable 'ednum' [-Wunused-variable]
170 | int ednum=a;
| ^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
14420 KB |
Output is correct |
2 |
Correct |
11 ms |
14420 KB |
Output is correct |
3 |
Correct |
10 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14364 KB |
Output is correct |
5 |
Correct |
17 ms |
16588 KB |
Output is correct |
6 |
Correct |
18 ms |
16540 KB |
Output is correct |
7 |
Correct |
18 ms |
16084 KB |
Output is correct |
8 |
Correct |
20 ms |
16808 KB |
Output is correct |
9 |
Correct |
24 ms |
16724 KB |
Output is correct |
10 |
Correct |
23 ms |
16768 KB |
Output is correct |
11 |
Correct |
20 ms |
16804 KB |
Output is correct |
12 |
Correct |
19 ms |
16804 KB |
Output is correct |
13 |
Correct |
20 ms |
16940 KB |
Output is correct |
14 |
Correct |
21 ms |
16924 KB |
Output is correct |
15 |
Correct |
20 ms |
16908 KB |
Output is correct |
16 |
Correct |
23 ms |
16872 KB |
Output is correct |
17 |
Correct |
25 ms |
16844 KB |
Output is correct |
18 |
Correct |
24 ms |
16816 KB |
Output is correct |
19 |
Correct |
20 ms |
16788 KB |
Output is correct |
20 |
Correct |
25 ms |
16816 KB |
Output is correct |
21 |
Correct |
19 ms |
16732 KB |
Output is correct |
22 |
Correct |
20 ms |
16720 KB |
Output is correct |
23 |
Correct |
19 ms |
16712 KB |
Output is correct |
24 |
Correct |
20 ms |
16808 KB |
Output is correct |
25 |
Correct |
25 ms |
16720 KB |
Output is correct |
26 |
Correct |
20 ms |
16752 KB |
Output is correct |
27 |
Correct |
19 ms |
16764 KB |
Output is correct |
28 |
Correct |
24 ms |
16712 KB |
Output is correct |
29 |
Correct |
26 ms |
16784 KB |
Output is correct |
30 |
Correct |
20 ms |
16724 KB |
Output is correct |
31 |
Correct |
24 ms |
16724 KB |
Output is correct |
32 |
Correct |
19 ms |
16724 KB |
Output is correct |
33 |
Correct |
19 ms |
17008 KB |
Output is correct |
34 |
Correct |
22 ms |
16988 KB |
Output is correct |
35 |
Correct |
19 ms |
16960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
14420 KB |
Output is correct |
2 |
Correct |
19 ms |
16832 KB |
Output is correct |
3 |
Correct |
21 ms |
16844 KB |
Output is correct |
4 |
Correct |
19 ms |
16852 KB |
Output is correct |
5 |
Correct |
651 ms |
126368 KB |
Output is correct |
6 |
Correct |
602 ms |
110560 KB |
Output is correct |
7 |
Correct |
618 ms |
100660 KB |
Output is correct |
8 |
Correct |
645 ms |
98424 KB |
Output is correct |
9 |
Correct |
566 ms |
102836 KB |
Output is correct |
10 |
Correct |
852 ms |
136008 KB |
Output is correct |
11 |
Correct |
841 ms |
136212 KB |
Output is correct |
12 |
Correct |
762 ms |
136056 KB |
Output is correct |
13 |
Correct |
824 ms |
135988 KB |
Output is correct |
14 |
Correct |
761 ms |
136232 KB |
Output is correct |
15 |
Correct |
940 ms |
148272 KB |
Output is correct |
16 |
Correct |
834 ms |
149212 KB |
Output is correct |
17 |
Correct |
912 ms |
147740 KB |
Output is correct |
18 |
Correct |
820 ms |
136620 KB |
Output is correct |
19 |
Correct |
850 ms |
136596 KB |
Output is correct |
20 |
Correct |
836 ms |
136736 KB |
Output is correct |
21 |
Correct |
652 ms |
135612 KB |
Output is correct |
22 |
Correct |
630 ms |
135808 KB |
Output is correct |
23 |
Correct |
646 ms |
135868 KB |
Output is correct |
24 |
Correct |
642 ms |
135864 KB |
Output is correct |
25 |
Correct |
701 ms |
137096 KB |
Output is correct |
26 |
Correct |
669 ms |
137116 KB |
Output is correct |
27 |
Correct |
686 ms |
137156 KB |
Output is correct |
28 |
Correct |
629 ms |
135844 KB |
Output is correct |
29 |
Correct |
631 ms |
135952 KB |
Output is correct |
30 |
Correct |
696 ms |
136156 KB |
Output is correct |
31 |
Correct |
631 ms |
136120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
14420 KB |
Output is correct |
2 |
Correct |
18 ms |
16980 KB |
Output is correct |
3 |
Correct |
20 ms |
16980 KB |
Output is correct |
4 |
Correct |
18 ms |
17060 KB |
Output is correct |
5 |
Correct |
560 ms |
114444 KB |
Output is correct |
6 |
Correct |
556 ms |
101720 KB |
Output is correct |
7 |
Correct |
745 ms |
121780 KB |
Output is correct |
8 |
Correct |
936 ms |
147800 KB |
Output is correct |
9 |
Correct |
949 ms |
147828 KB |
Output is correct |
10 |
Correct |
897 ms |
147772 KB |
Output is correct |
11 |
Correct |
781 ms |
148420 KB |
Output is correct |
12 |
Correct |
808 ms |
148544 KB |
Output is correct |
13 |
Correct |
843 ms |
148472 KB |
Output is correct |
14 |
Correct |
657 ms |
147748 KB |
Output is correct |
15 |
Correct |
606 ms |
147580 KB |
Output is correct |
16 |
Correct |
648 ms |
147852 KB |
Output is correct |
17 |
Correct |
643 ms |
147724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
14420 KB |
Output is correct |
2 |
Correct |
11 ms |
14420 KB |
Output is correct |
3 |
Correct |
10 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14364 KB |
Output is correct |
5 |
Correct |
17 ms |
16588 KB |
Output is correct |
6 |
Correct |
18 ms |
16540 KB |
Output is correct |
7 |
Correct |
18 ms |
16084 KB |
Output is correct |
8 |
Correct |
20 ms |
16808 KB |
Output is correct |
9 |
Correct |
24 ms |
16724 KB |
Output is correct |
10 |
Correct |
23 ms |
16768 KB |
Output is correct |
11 |
Correct |
20 ms |
16804 KB |
Output is correct |
12 |
Correct |
19 ms |
16804 KB |
Output is correct |
13 |
Correct |
20 ms |
16940 KB |
Output is correct |
14 |
Correct |
21 ms |
16924 KB |
Output is correct |
15 |
Correct |
20 ms |
16908 KB |
Output is correct |
16 |
Correct |
23 ms |
16872 KB |
Output is correct |
17 |
Correct |
25 ms |
16844 KB |
Output is correct |
18 |
Correct |
24 ms |
16816 KB |
Output is correct |
19 |
Correct |
20 ms |
16788 KB |
Output is correct |
20 |
Correct |
25 ms |
16816 KB |
Output is correct |
21 |
Correct |
19 ms |
16732 KB |
Output is correct |
22 |
Correct |
20 ms |
16720 KB |
Output is correct |
23 |
Correct |
19 ms |
16712 KB |
Output is correct |
24 |
Correct |
20 ms |
16808 KB |
Output is correct |
25 |
Correct |
25 ms |
16720 KB |
Output is correct |
26 |
Correct |
20 ms |
16752 KB |
Output is correct |
27 |
Correct |
19 ms |
16764 KB |
Output is correct |
28 |
Correct |
24 ms |
16712 KB |
Output is correct |
29 |
Correct |
26 ms |
16784 KB |
Output is correct |
30 |
Correct |
20 ms |
16724 KB |
Output is correct |
31 |
Correct |
24 ms |
16724 KB |
Output is correct |
32 |
Correct |
19 ms |
16724 KB |
Output is correct |
33 |
Correct |
19 ms |
17008 KB |
Output is correct |
34 |
Correct |
22 ms |
16988 KB |
Output is correct |
35 |
Correct |
19 ms |
16960 KB |
Output is correct |
36 |
Correct |
10 ms |
14420 KB |
Output is correct |
37 |
Correct |
19 ms |
16832 KB |
Output is correct |
38 |
Correct |
21 ms |
16844 KB |
Output is correct |
39 |
Correct |
19 ms |
16852 KB |
Output is correct |
40 |
Correct |
651 ms |
126368 KB |
Output is correct |
41 |
Correct |
602 ms |
110560 KB |
Output is correct |
42 |
Correct |
618 ms |
100660 KB |
Output is correct |
43 |
Correct |
645 ms |
98424 KB |
Output is correct |
44 |
Correct |
566 ms |
102836 KB |
Output is correct |
45 |
Correct |
852 ms |
136008 KB |
Output is correct |
46 |
Correct |
841 ms |
136212 KB |
Output is correct |
47 |
Correct |
762 ms |
136056 KB |
Output is correct |
48 |
Correct |
824 ms |
135988 KB |
Output is correct |
49 |
Correct |
761 ms |
136232 KB |
Output is correct |
50 |
Correct |
940 ms |
148272 KB |
Output is correct |
51 |
Correct |
834 ms |
149212 KB |
Output is correct |
52 |
Correct |
912 ms |
147740 KB |
Output is correct |
53 |
Correct |
820 ms |
136620 KB |
Output is correct |
54 |
Correct |
850 ms |
136596 KB |
Output is correct |
55 |
Correct |
836 ms |
136736 KB |
Output is correct |
56 |
Correct |
652 ms |
135612 KB |
Output is correct |
57 |
Correct |
630 ms |
135808 KB |
Output is correct |
58 |
Correct |
646 ms |
135868 KB |
Output is correct |
59 |
Correct |
642 ms |
135864 KB |
Output is correct |
60 |
Correct |
701 ms |
137096 KB |
Output is correct |
61 |
Correct |
669 ms |
137116 KB |
Output is correct |
62 |
Correct |
686 ms |
137156 KB |
Output is correct |
63 |
Correct |
629 ms |
135844 KB |
Output is correct |
64 |
Correct |
631 ms |
135952 KB |
Output is correct |
65 |
Correct |
696 ms |
136156 KB |
Output is correct |
66 |
Correct |
631 ms |
136120 KB |
Output is correct |
67 |
Correct |
12 ms |
14420 KB |
Output is correct |
68 |
Correct |
18 ms |
16980 KB |
Output is correct |
69 |
Correct |
20 ms |
16980 KB |
Output is correct |
70 |
Correct |
18 ms |
17060 KB |
Output is correct |
71 |
Correct |
560 ms |
114444 KB |
Output is correct |
72 |
Correct |
556 ms |
101720 KB |
Output is correct |
73 |
Correct |
745 ms |
121780 KB |
Output is correct |
74 |
Correct |
936 ms |
147800 KB |
Output is correct |
75 |
Correct |
949 ms |
147828 KB |
Output is correct |
76 |
Correct |
897 ms |
147772 KB |
Output is correct |
77 |
Correct |
781 ms |
148420 KB |
Output is correct |
78 |
Correct |
808 ms |
148544 KB |
Output is correct |
79 |
Correct |
843 ms |
148472 KB |
Output is correct |
80 |
Correct |
657 ms |
147748 KB |
Output is correct |
81 |
Correct |
606 ms |
147580 KB |
Output is correct |
82 |
Correct |
648 ms |
147852 KB |
Output is correct |
83 |
Correct |
643 ms |
147724 KB |
Output is correct |
84 |
Correct |
659 ms |
123112 KB |
Output is correct |
85 |
Correct |
560 ms |
107136 KB |
Output is correct |
86 |
Correct |
471 ms |
83972 KB |
Output is correct |
87 |
Correct |
838 ms |
134568 KB |
Output is correct |
88 |
Correct |
894 ms |
134588 KB |
Output is correct |
89 |
Correct |
864 ms |
134488 KB |
Output is correct |
90 |
Correct |
844 ms |
134528 KB |
Output is correct |
91 |
Correct |
882 ms |
134672 KB |
Output is correct |
92 |
Correct |
1201 ms |
143292 KB |
Output is correct |
93 |
Correct |
1157 ms |
145836 KB |
Output is correct |
94 |
Correct |
1020 ms |
135304 KB |
Output is correct |
95 |
Correct |
1067 ms |
135248 KB |
Output is correct |
96 |
Correct |
1086 ms |
135196 KB |
Output is correct |
97 |
Correct |
1006 ms |
135104 KB |
Output is correct |
98 |
Correct |
732 ms |
134520 KB |
Output is correct |
99 |
Correct |
758 ms |
134320 KB |
Output is correct |
100 |
Correct |
718 ms |
134332 KB |
Output is correct |
101 |
Correct |
724 ms |
134512 KB |
Output is correct |
102 |
Correct |
834 ms |
135676 KB |
Output is correct |
103 |
Correct |
803 ms |
135648 KB |
Output is correct |
104 |
Correct |
791 ms |
135536 KB |
Output is correct |
105 |
Correct |
781 ms |
134636 KB |
Output is correct |
106 |
Correct |
707 ms |
134568 KB |
Output is correct |
107 |
Correct |
740 ms |
134540 KB |
Output is correct |
108 |
Correct |
698 ms |
134524 KB |
Output is correct |