#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
int a,b;
}e[100001];
struct checkpoint{
int p,c;
}ch[100001];
struct citizen{
int s,t,x,y,idx;
}c[100001];
struct T{
int gold,silver;
};
int n,m,q,res[100001];
int p[100001][20],tin[100001],tout[100001],t;//lca
int root[100001],pos[100001],sz[100001],chain[100001],chainsize[100001],id;//hld
int l[100001],r[100001],kq[100001];//binary search
vector <int> ke[100001];
vector <citizen> ve[100001];
vector <T> st[100001];
T operator +(T a, T b){
return {a.gold+b.gold,a.silver+b.silver};
}
void update(int node, int l, int r, int x, int g, int s, int idx){
if (l>x||r<x||l>r)
return;
if (l==r){
st[idx][node].gold+=g;
st[idx][node].silver+=s;
return;
}
int mid=(l+r)>>1;
update(node<<1,l,mid,x,g,s,idx);
update(node<<1|1,mid+1,r,x,g,s,idx);
st[idx][node]=st[idx][node<<1]+st[idx][node<<1|1];
}
void update(int i, int mode){
if (!i)
return;
int u=ch[i].p;
update(1,1,chainsize[chain[u]],pos[u],(mode?1:-1),(mode?0:ch[i].c),chain[u]);
}
T get(int node, int l, int r, int u, int v, int idx){
if (l>v||r<u||l>r||u>v)
return {0,0};
if (l>=u&&r<=v)
return st[idx][node];
int mid=(l+r)>>1;
return get(node<<1,l,mid,u,v,idx)+get(node<<1|1,mid+1,r,u,v,idx);
}
void dfs(int u=1, int par=1){
tin[u]=++t;
sz[u]=1;
for (int v:ke[u])
if (v!=par){
p[v][0]=u;
for (int i=1;i<20;i++)
p[v][i]=p[p[v][i-1]][i-1];
dfs(v,u);
sz[u]+=sz[v];
}
tout[u]=t;
}
bool isancestor(int u, int v){
return (tin[u]<=tin[v]&&tout[u]>=tout[v]);
}
int lca(int u, int v){
if (isancestor(u,v))
return u;
if (isancestor(v,u))
return v;
for (int i=19;i>=0;i--)
if (p[u][i]&&!isancestor(p[u][i],v))
u=p[u][i];
return p[u][0];
}
void dfs2(int u=1){
if (!pos[u]){
pos[u]=1;
root[u]=u;
chain[u]=++id;
}
chainsize[chain[u]]++;
int mx=0,bigchild=-1;
for (int v:ke[u])
if (v!=p[u][0])
if (mx<sz[v]){
mx=sz[v];
bigchild=v;
}
if (bigchild!=-1){
pos[bigchild]=pos[u]+1;
chain[bigchild]=chain[u];
root[bigchild]=root[u];
}
for (int v:ke[u])
if (v!=p[u][0])
dfs2(v);
}
T get(int u, int v){
int l=lca(u,v);
T res;
res.gold=res.silver=0;
while (u){
if (isancestor(root[u],l)){
res=res+get(1,1,chainsize[chain[u]],pos[l]+1,pos[u],chain[u]);
break;
}
res=res+get(1,1,chainsize[chain[u]],1,pos[u],chain[u]);
u=p[root[u]][0];
}
swap(u,v);
while (u){
if (isancestor(root[u],l)){
res=res+get(1,1,chainsize[chain[u]],pos[l]+1,pos[u],chain[u]);
break;
}
res=res+get(1,1,chainsize[chain[u]],1,pos[u],chain[u]);
u=p[root[u]][0];
}
return res;
}
int32_t main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n >> m >> q;
for (int i=1;i<n;i++){
cin >> e[i].a >> e[i].b;
ke[e[i].a].push_back(e[i].b);
ke[e[i].b].push_back(e[i].a);
}
for (int i=1;i<=m;i++)
cin >> ch[i].p >> ch[i].c;
sort(ch+1,ch+m+1,[](checkpoint a, checkpoint b){
return a.c<b.c;
});
for (int i=1;i<=q;i++){
cin >> c[i].s >> c[i].t >> c[i].x >> c[i].y;
c[i].idx=i;
l[i]=1;
r[i]=m;
}
dfs();
dfs2();
for (int i=1;i<n;i++)
if (e[i].a==p[e[i].b][0])
swap(e[i].a,e[i].b);
for (int i=1;i<=m;i++)
ch[i].p=e[ch[i].p].a;
for (int i=1;i<=id;i++)
st[i].resize(chainsize[i]*4+1);
while (true){
bool change=false;
for (int i=1;i<=id;i++)
for (T &j:st[i])
j.gold=j.silver=0;
for (int i=1;i<=m;i++){
ve[i].clear();
update(i,1);
}
for (int i=1;i<=q;i++)
if (l[i]<=r[i]){
ve[(l[i]+r[i])>>1].push_back(c[i]);
change=true;
}
if (!change)
break;
for (int i=1;i<=m;i++){
update(i,0);
for (auto j:ve[i]){
T t=get(j.s,j.t);
if (t.silver<=j.y){
kq[j.idx]=i;
l[j.idx]=i+1;
}
else
r[j.idx]=i-1;
}
}
}
for (int i=1;i<=id;i++)
for (T &j:st[i])
j.gold=j.silver=0;
for (int i=1;i<=m;i++){
ve[i].clear();
update(i,1);
}
for (int i=1;i<=q;i++)
ve[kq[i]].push_back(c[i]);
for (int i=0;i<=m;i++){
update(i,0);
for (auto j:ve[i]){
T t=get(j.s,j.t);
res[j.idx]=max(j.x-t.gold,-1LL);
}
}
for (int i=1;i<=q;i++)
cout << res[i] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
13 ms |
8844 KB |
Output is correct |
6 |
Correct |
25 ms |
9324 KB |
Output is correct |
7 |
Correct |
15 ms |
9092 KB |
Output is correct |
8 |
Correct |
18 ms |
9428 KB |
Output is correct |
9 |
Correct |
19 ms |
9416 KB |
Output is correct |
10 |
Correct |
18 ms |
9428 KB |
Output is correct |
11 |
Correct |
22 ms |
9484 KB |
Output is correct |
12 |
Correct |
18 ms |
9484 KB |
Output is correct |
13 |
Correct |
33 ms |
9548 KB |
Output is correct |
14 |
Correct |
24 ms |
9524 KB |
Output is correct |
15 |
Correct |
25 ms |
9420 KB |
Output is correct |
16 |
Correct |
24 ms |
9448 KB |
Output is correct |
17 |
Correct |
29 ms |
9444 KB |
Output is correct |
18 |
Correct |
26 ms |
9424 KB |
Output is correct |
19 |
Correct |
10 ms |
9468 KB |
Output is correct |
20 |
Correct |
13 ms |
9512 KB |
Output is correct |
21 |
Correct |
10 ms |
9556 KB |
Output is correct |
22 |
Correct |
10 ms |
9556 KB |
Output is correct |
23 |
Correct |
18 ms |
9492 KB |
Output is correct |
24 |
Correct |
15 ms |
9516 KB |
Output is correct |
25 |
Correct |
14 ms |
9504 KB |
Output is correct |
26 |
Correct |
12 ms |
9496 KB |
Output is correct |
27 |
Correct |
16 ms |
9516 KB |
Output is correct |
28 |
Correct |
19 ms |
9484 KB |
Output is correct |
29 |
Correct |
13 ms |
9352 KB |
Output is correct |
30 |
Correct |
18 ms |
9452 KB |
Output is correct |
31 |
Correct |
23 ms |
9508 KB |
Output is correct |
32 |
Correct |
17 ms |
9472 KB |
Output is correct |
33 |
Correct |
22 ms |
9644 KB |
Output is correct |
34 |
Correct |
22 ms |
9528 KB |
Output is correct |
35 |
Correct |
24 ms |
9548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7384 KB |
Output is correct |
2 |
Correct |
17 ms |
9524 KB |
Output is correct |
3 |
Correct |
16 ms |
9508 KB |
Output is correct |
4 |
Correct |
16 ms |
9504 KB |
Output is correct |
5 |
Correct |
1975 ms |
100812 KB |
Output is correct |
6 |
Correct |
2280 ms |
121724 KB |
Output is correct |
7 |
Correct |
2562 ms |
118024 KB |
Output is correct |
8 |
Correct |
1804 ms |
97380 KB |
Output is correct |
9 |
Correct |
2065 ms |
94620 KB |
Output is correct |
10 |
Correct |
2918 ms |
136784 KB |
Output is correct |
11 |
Correct |
3036 ms |
136204 KB |
Output is correct |
12 |
Correct |
3096 ms |
136492 KB |
Output is correct |
13 |
Correct |
2818 ms |
135416 KB |
Output is correct |
14 |
Correct |
2911 ms |
137120 KB |
Output is correct |
15 |
Correct |
3036 ms |
141640 KB |
Output is correct |
16 |
Correct |
2697 ms |
142492 KB |
Output is correct |
17 |
Correct |
2966 ms |
140712 KB |
Output is correct |
18 |
Correct |
4214 ms |
136540 KB |
Output is correct |
19 |
Correct |
4009 ms |
136164 KB |
Output is correct |
20 |
Correct |
3902 ms |
136332 KB |
Output is correct |
21 |
Correct |
1432 ms |
139336 KB |
Output is correct |
22 |
Correct |
1312 ms |
139644 KB |
Output is correct |
23 |
Correct |
1398 ms |
141768 KB |
Output is correct |
24 |
Correct |
1534 ms |
140852 KB |
Output is correct |
25 |
Correct |
2176 ms |
136024 KB |
Output is correct |
26 |
Correct |
2142 ms |
133668 KB |
Output is correct |
27 |
Correct |
2095 ms |
138740 KB |
Output is correct |
28 |
Correct |
1350 ms |
136900 KB |
Output is correct |
29 |
Correct |
1231 ms |
132552 KB |
Output is correct |
30 |
Correct |
1494 ms |
126952 KB |
Output is correct |
31 |
Correct |
1463 ms |
128236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
21 ms |
9556 KB |
Output is correct |
3 |
Correct |
23 ms |
9544 KB |
Output is correct |
4 |
Correct |
27 ms |
9564 KB |
Output is correct |
5 |
Correct |
1552 ms |
104832 KB |
Output is correct |
6 |
Correct |
1432 ms |
105620 KB |
Output is correct |
7 |
Correct |
2195 ms |
108164 KB |
Output is correct |
8 |
Correct |
2849 ms |
143060 KB |
Output is correct |
9 |
Correct |
2876 ms |
142496 KB |
Output is correct |
10 |
Correct |
2647 ms |
142832 KB |
Output is correct |
11 |
Correct |
2367 ms |
142044 KB |
Output is correct |
12 |
Correct |
2421 ms |
142256 KB |
Output is correct |
13 |
Correct |
2402 ms |
142168 KB |
Output is correct |
14 |
Correct |
2356 ms |
144276 KB |
Output is correct |
15 |
Correct |
2414 ms |
145576 KB |
Output is correct |
16 |
Correct |
2351 ms |
143564 KB |
Output is correct |
17 |
Correct |
2291 ms |
144296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
13 ms |
8844 KB |
Output is correct |
6 |
Correct |
25 ms |
9324 KB |
Output is correct |
7 |
Correct |
15 ms |
9092 KB |
Output is correct |
8 |
Correct |
18 ms |
9428 KB |
Output is correct |
9 |
Correct |
19 ms |
9416 KB |
Output is correct |
10 |
Correct |
18 ms |
9428 KB |
Output is correct |
11 |
Correct |
22 ms |
9484 KB |
Output is correct |
12 |
Correct |
18 ms |
9484 KB |
Output is correct |
13 |
Correct |
33 ms |
9548 KB |
Output is correct |
14 |
Correct |
24 ms |
9524 KB |
Output is correct |
15 |
Correct |
25 ms |
9420 KB |
Output is correct |
16 |
Correct |
24 ms |
9448 KB |
Output is correct |
17 |
Correct |
29 ms |
9444 KB |
Output is correct |
18 |
Correct |
26 ms |
9424 KB |
Output is correct |
19 |
Correct |
10 ms |
9468 KB |
Output is correct |
20 |
Correct |
13 ms |
9512 KB |
Output is correct |
21 |
Correct |
10 ms |
9556 KB |
Output is correct |
22 |
Correct |
10 ms |
9556 KB |
Output is correct |
23 |
Correct |
18 ms |
9492 KB |
Output is correct |
24 |
Correct |
15 ms |
9516 KB |
Output is correct |
25 |
Correct |
14 ms |
9504 KB |
Output is correct |
26 |
Correct |
12 ms |
9496 KB |
Output is correct |
27 |
Correct |
16 ms |
9516 KB |
Output is correct |
28 |
Correct |
19 ms |
9484 KB |
Output is correct |
29 |
Correct |
13 ms |
9352 KB |
Output is correct |
30 |
Correct |
18 ms |
9452 KB |
Output is correct |
31 |
Correct |
23 ms |
9508 KB |
Output is correct |
32 |
Correct |
17 ms |
9472 KB |
Output is correct |
33 |
Correct |
22 ms |
9644 KB |
Output is correct |
34 |
Correct |
22 ms |
9528 KB |
Output is correct |
35 |
Correct |
24 ms |
9548 KB |
Output is correct |
36 |
Correct |
4 ms |
7384 KB |
Output is correct |
37 |
Correct |
17 ms |
9524 KB |
Output is correct |
38 |
Correct |
16 ms |
9508 KB |
Output is correct |
39 |
Correct |
16 ms |
9504 KB |
Output is correct |
40 |
Correct |
1975 ms |
100812 KB |
Output is correct |
41 |
Correct |
2280 ms |
121724 KB |
Output is correct |
42 |
Correct |
2562 ms |
118024 KB |
Output is correct |
43 |
Correct |
1804 ms |
97380 KB |
Output is correct |
44 |
Correct |
2065 ms |
94620 KB |
Output is correct |
45 |
Correct |
2918 ms |
136784 KB |
Output is correct |
46 |
Correct |
3036 ms |
136204 KB |
Output is correct |
47 |
Correct |
3096 ms |
136492 KB |
Output is correct |
48 |
Correct |
2818 ms |
135416 KB |
Output is correct |
49 |
Correct |
2911 ms |
137120 KB |
Output is correct |
50 |
Correct |
3036 ms |
141640 KB |
Output is correct |
51 |
Correct |
2697 ms |
142492 KB |
Output is correct |
52 |
Correct |
2966 ms |
140712 KB |
Output is correct |
53 |
Correct |
4214 ms |
136540 KB |
Output is correct |
54 |
Correct |
4009 ms |
136164 KB |
Output is correct |
55 |
Correct |
3902 ms |
136332 KB |
Output is correct |
56 |
Correct |
1432 ms |
139336 KB |
Output is correct |
57 |
Correct |
1312 ms |
139644 KB |
Output is correct |
58 |
Correct |
1398 ms |
141768 KB |
Output is correct |
59 |
Correct |
1534 ms |
140852 KB |
Output is correct |
60 |
Correct |
2176 ms |
136024 KB |
Output is correct |
61 |
Correct |
2142 ms |
133668 KB |
Output is correct |
62 |
Correct |
2095 ms |
138740 KB |
Output is correct |
63 |
Correct |
1350 ms |
136900 KB |
Output is correct |
64 |
Correct |
1231 ms |
132552 KB |
Output is correct |
65 |
Correct |
1494 ms |
126952 KB |
Output is correct |
66 |
Correct |
1463 ms |
128236 KB |
Output is correct |
67 |
Correct |
4 ms |
7380 KB |
Output is correct |
68 |
Correct |
21 ms |
9556 KB |
Output is correct |
69 |
Correct |
23 ms |
9544 KB |
Output is correct |
70 |
Correct |
27 ms |
9564 KB |
Output is correct |
71 |
Correct |
1552 ms |
104832 KB |
Output is correct |
72 |
Correct |
1432 ms |
105620 KB |
Output is correct |
73 |
Correct |
2195 ms |
108164 KB |
Output is correct |
74 |
Correct |
2849 ms |
143060 KB |
Output is correct |
75 |
Correct |
2876 ms |
142496 KB |
Output is correct |
76 |
Correct |
2647 ms |
142832 KB |
Output is correct |
77 |
Correct |
2367 ms |
142044 KB |
Output is correct |
78 |
Correct |
2421 ms |
142256 KB |
Output is correct |
79 |
Correct |
2402 ms |
142168 KB |
Output is correct |
80 |
Correct |
2356 ms |
144276 KB |
Output is correct |
81 |
Correct |
2414 ms |
145576 KB |
Output is correct |
82 |
Correct |
2351 ms |
143564 KB |
Output is correct |
83 |
Correct |
2291 ms |
144296 KB |
Output is correct |
84 |
Correct |
2207 ms |
97452 KB |
Output is correct |
85 |
Correct |
1896 ms |
96260 KB |
Output is correct |
86 |
Correct |
1724 ms |
94656 KB |
Output is correct |
87 |
Correct |
3299 ms |
135360 KB |
Output is correct |
88 |
Correct |
3346 ms |
134588 KB |
Output is correct |
89 |
Correct |
3402 ms |
135940 KB |
Output is correct |
90 |
Correct |
3103 ms |
135856 KB |
Output is correct |
91 |
Correct |
3098 ms |
135928 KB |
Output is correct |
92 |
Correct |
3625 ms |
139408 KB |
Output is correct |
93 |
Correct |
3814 ms |
140884 KB |
Output is correct |
94 |
Correct |
4266 ms |
135824 KB |
Output is correct |
95 |
Correct |
4275 ms |
135940 KB |
Output is correct |
96 |
Correct |
4321 ms |
135516 KB |
Output is correct |
97 |
Correct |
4113 ms |
135512 KB |
Output is correct |
98 |
Correct |
1555 ms |
140488 KB |
Output is correct |
99 |
Correct |
1855 ms |
138576 KB |
Output is correct |
100 |
Correct |
1766 ms |
138872 KB |
Output is correct |
101 |
Correct |
1660 ms |
141544 KB |
Output is correct |
102 |
Correct |
2106 ms |
135744 KB |
Output is correct |
103 |
Correct |
2207 ms |
136680 KB |
Output is correct |
104 |
Correct |
2467 ms |
136432 KB |
Output is correct |
105 |
Correct |
1267 ms |
128872 KB |
Output is correct |
106 |
Correct |
1532 ms |
136408 KB |
Output is correct |
107 |
Correct |
1613 ms |
126796 KB |
Output is correct |
108 |
Correct |
1641 ms |
127524 KB |
Output is correct |