#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
int n,m,q,u[100005],v[100005],road[100005],pos[400005];
int tin,in[200005],out[200005],lift[25][200005],szm,szq;
int l[100005],r[100005],gold[100005],sil[100005],vis[100005];
int frq[100005],bkfq[100005],sum[100005],ans[100005];
pair<int,int> ckpt[100005];
vector<pair<int,int> > grh[200005];
vector<int> st[100005];
pair<int,pair<int,int> > qry[100005];
void add(int x,int y,int w){
grh[x].push_back({y,w});
grh[y].push_back({x,w});
}
bool is(int x,int y){
return (in[x]<=in[y] && out[x]>=out[y]);
}
int lca(int x,int y){
if (is(x,y)) return x;
if (is(y,x)) return y;
for (int i=20;i>=0;i--){
if (lift[i][x] && !is(lift[i][x],y)) x=lift[i][x];
}
return lift[0][x];
}
void dfs(int x,int p){
in[x]=++tin; lift[0][x]=p;
for (int i=1;i<=20;i++) lift[i][x]=lift[i-1][lift[i-1][x]];
for (pair<int,int> i:grh[x]){
if (i.f==p) continue;
road[i.f]=i.second;
dfs(i.f,x);
}
out[x]=++tin;
pos[in[x]]=pos[out[x]]=x;
}
bool cmp(pair<int,pair<int,int>> x,pair<int,pair<int,int>> y){
if (x.s.f/szq!=y.s.f/szq) return x.s.f<y.s.f;
else return x.s.s<y.s.s;
}
int blck(int x){
return x/szm+(x%szm>0LL);
}
void upd(int x){
x=pos[x];
vis[x]^=1LL;
if (!road[x]) return;
if (vis[x]){
// cout<<"add "<<road[x]<<" "<<x<<'\n';
frq[road[x]]++; bkfq[blck(road[x])]++;
sum[blck(road[x])]+=ckpt[road[x]].f;
}
else {
//cout<<"del "<<road[x]<<" "<<x<<"\n";
frq[road[x]]--; bkfq[blck(road[x])]--;
sum[blck(road[x])]-=ckpt[road[x]].f;
}
}
signed main(){
cin>>n>>m>>q;
szm=(int)sqrt(n); szq=(int)sqrt(q);
for (int i=1;i<n;i++) cin>>u[i]>>v[i];
for (int i=1;i<=m;i++) cin>>ckpt[i].s>>ckpt[i].f;
sort(ckpt+1,ckpt+1+m);
for (int i=1;i<=m;i++){
st[ckpt[i].s].push_back(i);
}
for (int i=1;i<n;i++){
if (st[i].empty()) {
add(u[i],v[i],0);
continue;
}
int curr=u[i];
for (int j=0;j<st[i].size()-1;j++) {
add(curr,n+st[i][j],st[i][j]);
curr=n+st[i][j];
}
add(curr,v[i],st[i].back());
}
dfs(1,0);
for (int i=1;i<=q;i++){
cin>>l[i]>>r[i]>>gold[i]>>sil[i];
if (in[l[i]]>in[r[i]]) swap(l[i],r[i]);
int anc=lca(l[i],r[i]);
qry[i].f=i;
if (l[i]==anc) qry[i].s={in[l[i]],in[r[i]]};
else qry[i].s={out[l[i]],in[r[i]]};
}
sort(qry+1,qry+1+q,cmp);
int ptr=0; int ptl=1;
for (int i=1;i<=q;i++){
while (ptr>qry[i].s.s) upd(ptr--);
while (ptr<qry[i].s.s) upd(++ptr);
while (ptl>qry[i].s.f) upd(--ptl);
while (ptl<qry[i].s.f) upd(ptl++);
int anc=lca(l[qry[i].f],r[qry[i].f]);
bool ok=false;
if (l[qry[i].f]==anc) upd(in[anc]);
for (int j=1;j<=blck(m);j++){
if (ok) ans[qry[i].f]+=bkfq[j];
else if (sum[j]<=sil[qry[i].f]) sil[qry[i].f]-=sum[j];
else {
ok=true;
for (int k=szm*(j-1)+1;k<=min(m,szm*j);k++){
int d=min(sil[qry[i].f]/ckpt[k].f,frq[k]);
sil[qry[i].f]-=d*ckpt[k].f;
ans[qry[i].f]+=frq[k]-d;
}
}
}
if (l[qry[i].f]==anc) upd(in[anc]);
}
for (int i=1;i<=q;i++){
// cout<<sil[i]<<" ";
if (ans[i]>gold[i]) cout<<"-1\n";
else cout<<gold[i]-ans[i]<<"\n";
}
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:77:17: 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]
77 | for (int j=0;j<st[i].size()-1;j++) {
| ~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7484 KB |
Output is correct |
2 |
Correct |
3 ms |
7508 KB |
Output is correct |
3 |
Correct |
3 ms |
7488 KB |
Output is correct |
4 |
Correct |
4 ms |
7484 KB |
Output is correct |
5 |
Correct |
11 ms |
8736 KB |
Output is correct |
6 |
Correct |
12 ms |
8784 KB |
Output is correct |
7 |
Correct |
9 ms |
8524 KB |
Output is correct |
8 |
Correct |
13 ms |
8788 KB |
Output is correct |
9 |
Correct |
13 ms |
8776 KB |
Output is correct |
10 |
Correct |
12 ms |
8800 KB |
Output is correct |
11 |
Correct |
13 ms |
8788 KB |
Output is correct |
12 |
Correct |
13 ms |
8880 KB |
Output is correct |
13 |
Correct |
11 ms |
8968 KB |
Output is correct |
14 |
Correct |
11 ms |
8916 KB |
Output is correct |
15 |
Correct |
11 ms |
8904 KB |
Output is correct |
16 |
Correct |
11 ms |
8916 KB |
Output is correct |
17 |
Correct |
11 ms |
8928 KB |
Output is correct |
18 |
Correct |
11 ms |
8916 KB |
Output is correct |
19 |
Correct |
12 ms |
8764 KB |
Output is correct |
20 |
Correct |
11 ms |
8780 KB |
Output is correct |
21 |
Correct |
13 ms |
8768 KB |
Output is correct |
22 |
Correct |
11 ms |
8860 KB |
Output is correct |
23 |
Correct |
9 ms |
8988 KB |
Output is correct |
24 |
Correct |
9 ms |
8904 KB |
Output is correct |
25 |
Correct |
10 ms |
8916 KB |
Output is correct |
26 |
Correct |
8 ms |
8888 KB |
Output is correct |
27 |
Correct |
8 ms |
8788 KB |
Output is correct |
28 |
Correct |
10 ms |
8784 KB |
Output is correct |
29 |
Correct |
9 ms |
8776 KB |
Output is correct |
30 |
Correct |
12 ms |
8788 KB |
Output is correct |
31 |
Correct |
13 ms |
8888 KB |
Output is correct |
32 |
Correct |
12 ms |
8788 KB |
Output is correct |
33 |
Correct |
9 ms |
9044 KB |
Output is correct |
34 |
Correct |
9 ms |
9036 KB |
Output is correct |
35 |
Correct |
9 ms |
9044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7508 KB |
Output is correct |
2 |
Correct |
13 ms |
8788 KB |
Output is correct |
3 |
Correct |
12 ms |
8896 KB |
Output is correct |
4 |
Correct |
12 ms |
8788 KB |
Output is correct |
5 |
Incorrect |
3534 ms |
66052 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7508 KB |
Output is correct |
2 |
Correct |
9 ms |
9044 KB |
Output is correct |
3 |
Correct |
9 ms |
9036 KB |
Output is correct |
4 |
Correct |
9 ms |
9032 KB |
Output is correct |
5 |
Incorrect |
845 ms |
65260 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7484 KB |
Output is correct |
2 |
Correct |
3 ms |
7508 KB |
Output is correct |
3 |
Correct |
3 ms |
7488 KB |
Output is correct |
4 |
Correct |
4 ms |
7484 KB |
Output is correct |
5 |
Correct |
11 ms |
8736 KB |
Output is correct |
6 |
Correct |
12 ms |
8784 KB |
Output is correct |
7 |
Correct |
9 ms |
8524 KB |
Output is correct |
8 |
Correct |
13 ms |
8788 KB |
Output is correct |
9 |
Correct |
13 ms |
8776 KB |
Output is correct |
10 |
Correct |
12 ms |
8800 KB |
Output is correct |
11 |
Correct |
13 ms |
8788 KB |
Output is correct |
12 |
Correct |
13 ms |
8880 KB |
Output is correct |
13 |
Correct |
11 ms |
8968 KB |
Output is correct |
14 |
Correct |
11 ms |
8916 KB |
Output is correct |
15 |
Correct |
11 ms |
8904 KB |
Output is correct |
16 |
Correct |
11 ms |
8916 KB |
Output is correct |
17 |
Correct |
11 ms |
8928 KB |
Output is correct |
18 |
Correct |
11 ms |
8916 KB |
Output is correct |
19 |
Correct |
12 ms |
8764 KB |
Output is correct |
20 |
Correct |
11 ms |
8780 KB |
Output is correct |
21 |
Correct |
13 ms |
8768 KB |
Output is correct |
22 |
Correct |
11 ms |
8860 KB |
Output is correct |
23 |
Correct |
9 ms |
8988 KB |
Output is correct |
24 |
Correct |
9 ms |
8904 KB |
Output is correct |
25 |
Correct |
10 ms |
8916 KB |
Output is correct |
26 |
Correct |
8 ms |
8888 KB |
Output is correct |
27 |
Correct |
8 ms |
8788 KB |
Output is correct |
28 |
Correct |
10 ms |
8784 KB |
Output is correct |
29 |
Correct |
9 ms |
8776 KB |
Output is correct |
30 |
Correct |
12 ms |
8788 KB |
Output is correct |
31 |
Correct |
13 ms |
8888 KB |
Output is correct |
32 |
Correct |
12 ms |
8788 KB |
Output is correct |
33 |
Correct |
9 ms |
9044 KB |
Output is correct |
34 |
Correct |
9 ms |
9036 KB |
Output is correct |
35 |
Correct |
9 ms |
9044 KB |
Output is correct |
36 |
Correct |
3 ms |
7508 KB |
Output is correct |
37 |
Correct |
13 ms |
8788 KB |
Output is correct |
38 |
Correct |
12 ms |
8896 KB |
Output is correct |
39 |
Correct |
12 ms |
8788 KB |
Output is correct |
40 |
Incorrect |
3534 ms |
66052 KB |
Output isn't correct |
41 |
Halted |
0 ms |
0 KB |
- |