#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
struct edge{
int ind,cost;
};
struct query{
int s,t;
long long x,y;
int l,r;
};
int n,m,q,tt,dist[MAXN],costs[MAXN];
long long ans[MAXN];
int a[MAXN],b[MAXN],fr[MAXN];
int from[MAXN],to[MAXN],ret[MAXN];
vector<int> euler,w[MAXN];
vector< pair<int,int> > v[MAXN];
edge e[MAXN];
query qs[MAXN];
bool cmp(edge fr,edge sc){
return fr.cost<sc.cost;
}
int dp[4*MAXN][20];
bool u[4*MAXN][20];
int lg[4*MAXN],power[20];
void calc(){
power[0]=1;
for(int i=1;i<20;i++)power[i]=power[i-1]*2;
lg[1]=0;
for(int i=2;i<=4*n;i++)lg[i]=lg[i/2]+1;
}
int rmq(int i,int j){
if(j==0)return euler[i];
if(u[i][j])return dp[i][j];
u[i][j]=true;
dp[i][j]=min( rmq(i,j-1) , rmq(i+power[j-1],j-1) );
return dp[i][j];
}
int getmin(int l,int r){
int len=r-l+1;
return min( rmq(l,lg[len]) , rmq(r-power[lg[len]]+1,lg[len]) );
}
int lca(int x,int y){
if(fr[x]>fr[y])swap(x,y);
return ret[ getmin(fr[x],fr[y]) ];
}
long long tree[4*MAXN];
void update(int v,int l,int r,int ll,int rr,long long val){
if(ll>rr)return;
if(l==ll and r==rr){
tree[v]+=val;
}else{
int tt=(l+r)/2;
update(2*v,l,tt,ll,min(tt,rr),val);
update(2*v+1,tt+1,r,max(tt+1,ll),rr,val);
}
}
long long getval(int v,int l,int r,int pos){
if(l==r)return tree[v];
int tt=(l+r)/2;
if(pos<=tt)return getval(2*v,l,tt,pos)+tree[v];
else return getval(2*v+1,tt+1,r,pos)+tree[v];
}
long long getdist(int x,int y){
return getval(1,1,n,from[x]) + getval(1,1,n,from[y]) - 2*getval(1,1,n,from[lca(x,y)]);
}
void dfs(int x,int p,int dd){
tt++; from[x]=tt; ret[tt]=x;
fr[x]=int(euler.size());
euler.push_back(from[x]);
dist[x]=dd;
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p)continue;
dfs(v[x][i].first,x,dd+costs[v[x][i].second]);
euler.push_back(from[x]);
}
to[x]=tt;
}
void parallel_binary(){
for(int i=0;i<=m;i++)w[i].clear();
for(int i=1;i<=q;i++){
if(qs[i].l+1<qs[i].r){
w[(qs[i].l+qs[i].r)/2].push_back(i);
}
}
for(int i=1;i<=4*n;i++)tree[i]=0;
for(int i=0;i<=m;i++){
if(i>0)update(1,1,n,from[b[e[i].ind]],to[b[e[i].ind]],e[i].cost);
for(int f:w[i]){
if(getdist(qs[f].s,qs[f].t)<=qs[f].y){
qs[f].l=(qs[f].l+qs[f].r)/2;
}else{
qs[f].r=(qs[f].l+qs[f].r)/2;
}
}
}
}
void find_sol(){
for(int i=0;i<=m;i++)w[i].clear();
for(int i=1;i<=q;i++){
w[qs[i].l].push_back(i);
}
for(int i=1;i<=4*n;i++)tree[i]=0;
for(int i=0;i<=m;i++){
if(i>0)update(1,1,n,from[b[e[i].ind]],to[b[e[i].ind]],1);
for(int f:w[i]){
ans[f]=dist[qs[f].s]+dist[qs[f].t]-2*dist[lca(qs[f].s,qs[f].t)] - getdist(qs[f].s,qs[f].t);
}
}
}
int main(){
cin>>n>>m>>q;
calc();
for(int i=1;i<=n-1;i++){
cin>>a[i]>>b[i];
v[a[i]].push_back({b[i],i});
v[b[i]].push_back({a[i],i});
}
for(int i=1;i<=m;i++){
cin>>e[i].ind>>e[i].cost;
costs[e[i].ind]++;
}
sort(e+1,e+m+1,cmp);
dfs(1,0,0);
for(int i=1;i<=n-1;i++){
if(from[a[i]]>from[b[i]])swap(a[i],b[i]);
}
for(int i=1;i<=q;i++){
cin>>qs[i].s>>qs[i].t>>qs[i].x>>qs[i].y;
qs[i].l=0;
qs[i].r=m+1;
}
for(int i=1;i<=17;i++){
parallel_binary();
}
find_sol();
for(int i=1;i<=q;i++){
ans[i]=qs[i].x-ans[i];
if(ans[i]<0)cout<<"-1\n";
else cout<<ans[i]<<"\n";
}
return 0;
}
Compilation message
currencies.cpp: In function 'void dfs(int, int, int)':
currencies.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
16732 KB |
Output is correct |
2 |
Correct |
2 ms |
16848 KB |
Output is correct |
3 |
Correct |
2 ms |
16732 KB |
Output is correct |
4 |
Correct |
3 ms |
16732 KB |
Output is correct |
5 |
Correct |
12 ms |
16980 KB |
Output is correct |
6 |
Correct |
15 ms |
17244 KB |
Output is correct |
7 |
Correct |
13 ms |
17240 KB |
Output is correct |
8 |
Correct |
19 ms |
17244 KB |
Output is correct |
9 |
Correct |
15 ms |
17244 KB |
Output is correct |
10 |
Correct |
16 ms |
17244 KB |
Output is correct |
11 |
Correct |
16 ms |
17264 KB |
Output is correct |
12 |
Correct |
15 ms |
17244 KB |
Output is correct |
13 |
Correct |
16 ms |
17244 KB |
Output is correct |
14 |
Correct |
17 ms |
17604 KB |
Output is correct |
15 |
Correct |
17 ms |
17244 KB |
Output is correct |
16 |
Correct |
17 ms |
17240 KB |
Output is correct |
17 |
Correct |
17 ms |
17244 KB |
Output is correct |
18 |
Correct |
17 ms |
17244 KB |
Output is correct |
19 |
Correct |
14 ms |
17244 KB |
Output is correct |
20 |
Correct |
14 ms |
17244 KB |
Output is correct |
21 |
Correct |
14 ms |
17244 KB |
Output is correct |
22 |
Correct |
14 ms |
17220 KB |
Output is correct |
23 |
Correct |
13 ms |
17240 KB |
Output is correct |
24 |
Correct |
13 ms |
17244 KB |
Output is correct |
25 |
Correct |
13 ms |
17368 KB |
Output is correct |
26 |
Correct |
12 ms |
17244 KB |
Output is correct |
27 |
Correct |
12 ms |
17104 KB |
Output is correct |
28 |
Correct |
14 ms |
17368 KB |
Output is correct |
29 |
Correct |
12 ms |
17244 KB |
Output is correct |
30 |
Correct |
15 ms |
17228 KB |
Output is correct |
31 |
Correct |
16 ms |
17244 KB |
Output is correct |
32 |
Correct |
15 ms |
17244 KB |
Output is correct |
33 |
Correct |
15 ms |
17244 KB |
Output is correct |
34 |
Correct |
15 ms |
17244 KB |
Output is correct |
35 |
Correct |
15 ms |
17364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
16728 KB |
Output is correct |
2 |
Correct |
15 ms |
17244 KB |
Output is correct |
3 |
Correct |
16 ms |
17240 KB |
Output is correct |
4 |
Correct |
16 ms |
17500 KB |
Output is correct |
5 |
Correct |
1095 ms |
52964 KB |
Output is correct |
6 |
Correct |
1197 ms |
49216 KB |
Output is correct |
7 |
Correct |
1177 ms |
51716 KB |
Output is correct |
8 |
Correct |
1002 ms |
49300 KB |
Output is correct |
9 |
Correct |
924 ms |
49112 KB |
Output is correct |
10 |
Correct |
1435 ms |
57720 KB |
Output is correct |
11 |
Correct |
1493 ms |
57608 KB |
Output is correct |
12 |
Correct |
1537 ms |
57592 KB |
Output is correct |
13 |
Correct |
1503 ms |
57536 KB |
Output is correct |
14 |
Correct |
1575 ms |
57840 KB |
Output is correct |
15 |
Correct |
1644 ms |
65044 KB |
Output is correct |
16 |
Correct |
1681 ms |
65112 KB |
Output is correct |
17 |
Correct |
1551 ms |
56348 KB |
Output is correct |
18 |
Correct |
1670 ms |
57544 KB |
Output is correct |
19 |
Correct |
1626 ms |
57544 KB |
Output is correct |
20 |
Correct |
1666 ms |
57424 KB |
Output is correct |
21 |
Correct |
1566 ms |
57516 KB |
Output is correct |
22 |
Correct |
1536 ms |
57544 KB |
Output is correct |
23 |
Correct |
1481 ms |
57524 KB |
Output is correct |
24 |
Correct |
1551 ms |
57956 KB |
Output is correct |
25 |
Correct |
1355 ms |
58048 KB |
Output is correct |
26 |
Correct |
1105 ms |
57720 KB |
Output is correct |
27 |
Correct |
1167 ms |
58388 KB |
Output is correct |
28 |
Correct |
757 ms |
41756 KB |
Output is correct |
29 |
Correct |
754 ms |
38676 KB |
Output is correct |
30 |
Correct |
907 ms |
55744 KB |
Output is correct |
31 |
Correct |
892 ms |
55852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
16732 KB |
Output is correct |
2 |
Correct |
15 ms |
17352 KB |
Output is correct |
3 |
Correct |
15 ms |
17360 KB |
Output is correct |
4 |
Correct |
15 ms |
17240 KB |
Output is correct |
5 |
Correct |
903 ms |
49848 KB |
Output is correct |
6 |
Correct |
875 ms |
49060 KB |
Output is correct |
7 |
Correct |
1120 ms |
44048 KB |
Output is correct |
8 |
Correct |
1496 ms |
55244 KB |
Output is correct |
9 |
Correct |
1517 ms |
55216 KB |
Output is correct |
10 |
Correct |
1554 ms |
55196 KB |
Output is correct |
11 |
Correct |
1213 ms |
55116 KB |
Output is correct |
12 |
Correct |
1220 ms |
55240 KB |
Output is correct |
13 |
Correct |
1265 ms |
55416 KB |
Output is correct |
14 |
Correct |
768 ms |
50108 KB |
Output is correct |
15 |
Correct |
774 ms |
50036 KB |
Output is correct |
16 |
Correct |
858 ms |
55304 KB |
Output is correct |
17 |
Correct |
916 ms |
55080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
16732 KB |
Output is correct |
2 |
Correct |
2 ms |
16848 KB |
Output is correct |
3 |
Correct |
2 ms |
16732 KB |
Output is correct |
4 |
Correct |
3 ms |
16732 KB |
Output is correct |
5 |
Correct |
12 ms |
16980 KB |
Output is correct |
6 |
Correct |
15 ms |
17244 KB |
Output is correct |
7 |
Correct |
13 ms |
17240 KB |
Output is correct |
8 |
Correct |
19 ms |
17244 KB |
Output is correct |
9 |
Correct |
15 ms |
17244 KB |
Output is correct |
10 |
Correct |
16 ms |
17244 KB |
Output is correct |
11 |
Correct |
16 ms |
17264 KB |
Output is correct |
12 |
Correct |
15 ms |
17244 KB |
Output is correct |
13 |
Correct |
16 ms |
17244 KB |
Output is correct |
14 |
Correct |
17 ms |
17604 KB |
Output is correct |
15 |
Correct |
17 ms |
17244 KB |
Output is correct |
16 |
Correct |
17 ms |
17240 KB |
Output is correct |
17 |
Correct |
17 ms |
17244 KB |
Output is correct |
18 |
Correct |
17 ms |
17244 KB |
Output is correct |
19 |
Correct |
14 ms |
17244 KB |
Output is correct |
20 |
Correct |
14 ms |
17244 KB |
Output is correct |
21 |
Correct |
14 ms |
17244 KB |
Output is correct |
22 |
Correct |
14 ms |
17220 KB |
Output is correct |
23 |
Correct |
13 ms |
17240 KB |
Output is correct |
24 |
Correct |
13 ms |
17244 KB |
Output is correct |
25 |
Correct |
13 ms |
17368 KB |
Output is correct |
26 |
Correct |
12 ms |
17244 KB |
Output is correct |
27 |
Correct |
12 ms |
17104 KB |
Output is correct |
28 |
Correct |
14 ms |
17368 KB |
Output is correct |
29 |
Correct |
12 ms |
17244 KB |
Output is correct |
30 |
Correct |
15 ms |
17228 KB |
Output is correct |
31 |
Correct |
16 ms |
17244 KB |
Output is correct |
32 |
Correct |
15 ms |
17244 KB |
Output is correct |
33 |
Correct |
15 ms |
17244 KB |
Output is correct |
34 |
Correct |
15 ms |
17244 KB |
Output is correct |
35 |
Correct |
15 ms |
17364 KB |
Output is correct |
36 |
Correct |
2 ms |
16728 KB |
Output is correct |
37 |
Correct |
15 ms |
17244 KB |
Output is correct |
38 |
Correct |
16 ms |
17240 KB |
Output is correct |
39 |
Correct |
16 ms |
17500 KB |
Output is correct |
40 |
Correct |
1095 ms |
52964 KB |
Output is correct |
41 |
Correct |
1197 ms |
49216 KB |
Output is correct |
42 |
Correct |
1177 ms |
51716 KB |
Output is correct |
43 |
Correct |
1002 ms |
49300 KB |
Output is correct |
44 |
Correct |
924 ms |
49112 KB |
Output is correct |
45 |
Correct |
1435 ms |
57720 KB |
Output is correct |
46 |
Correct |
1493 ms |
57608 KB |
Output is correct |
47 |
Correct |
1537 ms |
57592 KB |
Output is correct |
48 |
Correct |
1503 ms |
57536 KB |
Output is correct |
49 |
Correct |
1575 ms |
57840 KB |
Output is correct |
50 |
Correct |
1644 ms |
65044 KB |
Output is correct |
51 |
Correct |
1681 ms |
65112 KB |
Output is correct |
52 |
Correct |
1551 ms |
56348 KB |
Output is correct |
53 |
Correct |
1670 ms |
57544 KB |
Output is correct |
54 |
Correct |
1626 ms |
57544 KB |
Output is correct |
55 |
Correct |
1666 ms |
57424 KB |
Output is correct |
56 |
Correct |
1566 ms |
57516 KB |
Output is correct |
57 |
Correct |
1536 ms |
57544 KB |
Output is correct |
58 |
Correct |
1481 ms |
57524 KB |
Output is correct |
59 |
Correct |
1551 ms |
57956 KB |
Output is correct |
60 |
Correct |
1355 ms |
58048 KB |
Output is correct |
61 |
Correct |
1105 ms |
57720 KB |
Output is correct |
62 |
Correct |
1167 ms |
58388 KB |
Output is correct |
63 |
Correct |
757 ms |
41756 KB |
Output is correct |
64 |
Correct |
754 ms |
38676 KB |
Output is correct |
65 |
Correct |
907 ms |
55744 KB |
Output is correct |
66 |
Correct |
892 ms |
55852 KB |
Output is correct |
67 |
Correct |
2 ms |
16732 KB |
Output is correct |
68 |
Correct |
15 ms |
17352 KB |
Output is correct |
69 |
Correct |
15 ms |
17360 KB |
Output is correct |
70 |
Correct |
15 ms |
17240 KB |
Output is correct |
71 |
Correct |
903 ms |
49848 KB |
Output is correct |
72 |
Correct |
875 ms |
49060 KB |
Output is correct |
73 |
Correct |
1120 ms |
44048 KB |
Output is correct |
74 |
Correct |
1496 ms |
55244 KB |
Output is correct |
75 |
Correct |
1517 ms |
55216 KB |
Output is correct |
76 |
Correct |
1554 ms |
55196 KB |
Output is correct |
77 |
Correct |
1213 ms |
55116 KB |
Output is correct |
78 |
Correct |
1220 ms |
55240 KB |
Output is correct |
79 |
Correct |
1265 ms |
55416 KB |
Output is correct |
80 |
Correct |
768 ms |
50108 KB |
Output is correct |
81 |
Correct |
774 ms |
50036 KB |
Output is correct |
82 |
Correct |
858 ms |
55304 KB |
Output is correct |
83 |
Correct |
916 ms |
55080 KB |
Output is correct |
84 |
Correct |
1036 ms |
49452 KB |
Output is correct |
85 |
Correct |
1002 ms |
43148 KB |
Output is correct |
86 |
Correct |
887 ms |
42644 KB |
Output is correct |
87 |
Correct |
1489 ms |
57232 KB |
Output is correct |
88 |
Correct |
1542 ms |
57404 KB |
Output is correct |
89 |
Correct |
1514 ms |
57304 KB |
Output is correct |
90 |
Correct |
1508 ms |
57284 KB |
Output is correct |
91 |
Correct |
1631 ms |
57304 KB |
Output is correct |
92 |
Correct |
1586 ms |
56972 KB |
Output is correct |
93 |
Correct |
1635 ms |
56104 KB |
Output is correct |
94 |
Correct |
1743 ms |
57448 KB |
Output is correct |
95 |
Correct |
1637 ms |
57588 KB |
Output is correct |
96 |
Correct |
1702 ms |
57444 KB |
Output is correct |
97 |
Correct |
1712 ms |
57776 KB |
Output is correct |
98 |
Correct |
1528 ms |
57620 KB |
Output is correct |
99 |
Correct |
1478 ms |
57516 KB |
Output is correct |
100 |
Correct |
1532 ms |
57676 KB |
Output is correct |
101 |
Correct |
1508 ms |
57884 KB |
Output is correct |
102 |
Correct |
1149 ms |
58564 KB |
Output is correct |
103 |
Correct |
1202 ms |
58084 KB |
Output is correct |
104 |
Correct |
1246 ms |
58188 KB |
Output is correct |
105 |
Correct |
768 ms |
43464 KB |
Output is correct |
106 |
Correct |
790 ms |
42100 KB |
Output is correct |
107 |
Correct |
894 ms |
55236 KB |
Output is correct |
108 |
Correct |
918 ms |
55256 KB |
Output is correct |