#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
struct ST{
vector<int> st;
void init(int x){
st.resize(4*x);
}
void update(int v,int L,int R,int l,int r,int a){
if(L==l && r==R){
st[v]+=a;
return;
}
int m=(L+R)/2;
if(r<=m){
update(2*v+1,L,m,l,r,a);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,a);
}
else{
update(2*v+1,L,m,l,m,a);
update(2*v+2,m+1,R,m+1,r,a);
}
}
int query(int v,int L,int R,int t){
if(L==R){
return st[v];
}
int m=(L+R)/2;
if(t<=m){
return st[v]+query(2*v+1,L,m,t);
}
else{
return st[v]+query(2*v+2,m+1,R,t);
}
}
}st;
struct no{
vector<int> ch;
int in,out;
int as[18]={0};
};
int cnt=0;
vector<no> v;
void dfs(int r,int f){
cnt++;
v[r].as[0]=f;
v[r].in=cnt;
for(auto h:v[r].ch){
if(h!=f){
dfs(h,r);
}
}
v[r].out=cnt;
}
bool as(int a,int b){
return v[a].in<=v[b].in && v[a].out>=v[b].out;
}
int lca(int a,int b){
if(as(a,b)){
return a;
}
for(int i=17;i>=0;i--){
if(!as(v[a].as[i],b)){
a=v[a].as[i];
}
}
return v[a].as[0];
}
vector<pair<int,int> > z;
struct QU{
int a,b,l;
int c,d;
};
vector<QU> x;
int n;
vector<vector<int> > rf;
void cd(int l,int r,vector<int>& a){
if(a.empty()){
return;
}
if(l==r){
rf[l]=a;
return;
}
int m=(l+r)/2;
for(int i=l;i<=m;i++){
st.update(0,0,n,v[z[i].sc].in,v[z[i].sc].out,z[i].fs);
}
vector<int> b,c;
for(auto h:a){
int a=st.query(0,0,n,v[x[h].a].in)+st.query(0,0,n,v[x[h].b].in)-2*st.query(0,0,n,v[x[h].l].in);
if(a<=x[h].d){
c.push_back(h);
}
else{
b.push_back(h);
}
}
cd(m+1,r,c);
for(int i=l;i<=m;i++){
st.update(0,0,n,v[z[i].sc].in,v[z[i].sc].out,-z[i].fs);
}
cd(l,m,b);
}
signed main(){
AquA;
int m,q;
cin >> n >> m >> q;
v.resize(n);
st.init(n+1);
vector<pair<int,int> > eg(n);
for(int i=1;i<n;i++){
int a,b;
cin >> a >> b;
a--;
b--;
eg[i]={a,b};
v[a].ch.push_back(b);
v[b].ch.push_back(a);
}
dfs(0,0);
for(int i=1;i<18;i++){
for(int j=0;j<n;j++){
v[j].as[i]=v[v[j].as[i-1]].as[i-1];
}
}
for(auto &h:eg){
if(v[h.fs].as[0]!=h.sc){
swap(h.fs,h.sc);
}
}
z.resize(m);
for(int i=0;i<m;i++){
int a;
cin >> a >> z[i].fs;
z[i].sc=eg[a].fs;
}
sort(z.begin(),z.end());
x.resize(q);
for(int i=0;i<q;i++){
cin >> x[i].a >> x[i].b >> x[i].c >> x[i].d;
x[i].a--;
x[i].b--;
x[i].l=lca(x[i].a,x[i].b);
}
vector<int> sw(q);
iota(sw.begin(),sw.end(),0);
rf.resize(m+1);
cd(0,m,sw);
ST st2;
st2.init(n+1);
vector<int> ans(q);
for(int i=m;i>=0;i--){
if(i!=m){
st2.update(0,0,n,v[z[i].sc].in,v[z[i].sc].out,1);
}
for(auto h:rf[i]){
ans[h]=x[h].c-(st2.query(0,0,n,v[x[h].a].in)+st2.query(0,0,n,v[x[h].b].in)-2*st2.query(0,0,n,v[x[h].l].in));
}
}
for(auto h:ans){
if(h<0){
cout << -1 << '\n';
}
else{
cout << h << "\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
6 ms |
1108 KB |
Output is correct |
6 |
Correct |
7 ms |
1236 KB |
Output is correct |
7 |
Correct |
6 ms |
980 KB |
Output is correct |
8 |
Correct |
8 ms |
1196 KB |
Output is correct |
9 |
Correct |
8 ms |
1236 KB |
Output is correct |
10 |
Correct |
8 ms |
1196 KB |
Output is correct |
11 |
Correct |
8 ms |
1276 KB |
Output is correct |
12 |
Correct |
7 ms |
1236 KB |
Output is correct |
13 |
Correct |
8 ms |
1236 KB |
Output is correct |
14 |
Correct |
10 ms |
1300 KB |
Output is correct |
15 |
Correct |
8 ms |
1168 KB |
Output is correct |
16 |
Correct |
11 ms |
1236 KB |
Output is correct |
17 |
Correct |
8 ms |
1224 KB |
Output is correct |
18 |
Correct |
8 ms |
1236 KB |
Output is correct |
19 |
Correct |
7 ms |
1236 KB |
Output is correct |
20 |
Correct |
7 ms |
1236 KB |
Output is correct |
21 |
Correct |
7 ms |
1236 KB |
Output is correct |
22 |
Correct |
7 ms |
1224 KB |
Output is correct |
23 |
Correct |
6 ms |
1180 KB |
Output is correct |
24 |
Correct |
6 ms |
1236 KB |
Output is correct |
25 |
Correct |
6 ms |
1236 KB |
Output is correct |
26 |
Correct |
5 ms |
1232 KB |
Output is correct |
27 |
Correct |
4 ms |
1236 KB |
Output is correct |
28 |
Correct |
5 ms |
1236 KB |
Output is correct |
29 |
Correct |
6 ms |
1304 KB |
Output is correct |
30 |
Correct |
8 ms |
1228 KB |
Output is correct |
31 |
Correct |
7 ms |
1236 KB |
Output is correct |
32 |
Correct |
8 ms |
1236 KB |
Output is correct |
33 |
Correct |
8 ms |
1252 KB |
Output is correct |
34 |
Correct |
9 ms |
1236 KB |
Output is correct |
35 |
Correct |
8 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
7 ms |
1236 KB |
Output is correct |
3 |
Correct |
8 ms |
1272 KB |
Output is correct |
4 |
Correct |
7 ms |
1236 KB |
Output is correct |
5 |
Correct |
535 ms |
42628 KB |
Output is correct |
6 |
Correct |
712 ms |
38188 KB |
Output is correct |
7 |
Correct |
667 ms |
39548 KB |
Output is correct |
8 |
Correct |
536 ms |
37948 KB |
Output is correct |
9 |
Correct |
534 ms |
37688 KB |
Output is correct |
10 |
Correct |
813 ms |
47060 KB |
Output is correct |
11 |
Correct |
823 ms |
47052 KB |
Output is correct |
12 |
Correct |
792 ms |
47300 KB |
Output is correct |
13 |
Correct |
810 ms |
47092 KB |
Output is correct |
14 |
Correct |
812 ms |
47192 KB |
Output is correct |
15 |
Correct |
1089 ms |
50908 KB |
Output is correct |
16 |
Correct |
999 ms |
51208 KB |
Output is correct |
17 |
Correct |
1012 ms |
50660 KB |
Output is correct |
18 |
Correct |
943 ms |
47064 KB |
Output is correct |
19 |
Correct |
992 ms |
47128 KB |
Output is correct |
20 |
Correct |
959 ms |
46916 KB |
Output is correct |
21 |
Correct |
768 ms |
47880 KB |
Output is correct |
22 |
Correct |
834 ms |
48080 KB |
Output is correct |
23 |
Correct |
815 ms |
49472 KB |
Output is correct |
24 |
Correct |
806 ms |
47464 KB |
Output is correct |
25 |
Correct |
645 ms |
48068 KB |
Output is correct |
26 |
Correct |
586 ms |
48460 KB |
Output is correct |
27 |
Correct |
632 ms |
48232 KB |
Output is correct |
28 |
Correct |
301 ms |
48488 KB |
Output is correct |
29 |
Correct |
311 ms |
48076 KB |
Output is correct |
30 |
Correct |
424 ms |
47872 KB |
Output is correct |
31 |
Correct |
454 ms |
48044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
1236 KB |
Output is correct |
3 |
Correct |
8 ms |
1244 KB |
Output is correct |
4 |
Correct |
8 ms |
1252 KB |
Output is correct |
5 |
Correct |
630 ms |
45100 KB |
Output is correct |
6 |
Correct |
684 ms |
43776 KB |
Output is correct |
7 |
Correct |
752 ms |
34280 KB |
Output is correct |
8 |
Correct |
987 ms |
51236 KB |
Output is correct |
9 |
Correct |
998 ms |
51220 KB |
Output is correct |
10 |
Correct |
1036 ms |
51264 KB |
Output is correct |
11 |
Correct |
793 ms |
51276 KB |
Output is correct |
12 |
Correct |
738 ms |
51276 KB |
Output is correct |
13 |
Correct |
802 ms |
51056 KB |
Output is correct |
14 |
Correct |
473 ms |
50180 KB |
Output is correct |
15 |
Correct |
442 ms |
49888 KB |
Output is correct |
16 |
Correct |
551 ms |
50652 KB |
Output is correct |
17 |
Correct |
520 ms |
50336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
6 ms |
1108 KB |
Output is correct |
6 |
Correct |
7 ms |
1236 KB |
Output is correct |
7 |
Correct |
6 ms |
980 KB |
Output is correct |
8 |
Correct |
8 ms |
1196 KB |
Output is correct |
9 |
Correct |
8 ms |
1236 KB |
Output is correct |
10 |
Correct |
8 ms |
1196 KB |
Output is correct |
11 |
Correct |
8 ms |
1276 KB |
Output is correct |
12 |
Correct |
7 ms |
1236 KB |
Output is correct |
13 |
Correct |
8 ms |
1236 KB |
Output is correct |
14 |
Correct |
10 ms |
1300 KB |
Output is correct |
15 |
Correct |
8 ms |
1168 KB |
Output is correct |
16 |
Correct |
11 ms |
1236 KB |
Output is correct |
17 |
Correct |
8 ms |
1224 KB |
Output is correct |
18 |
Correct |
8 ms |
1236 KB |
Output is correct |
19 |
Correct |
7 ms |
1236 KB |
Output is correct |
20 |
Correct |
7 ms |
1236 KB |
Output is correct |
21 |
Correct |
7 ms |
1236 KB |
Output is correct |
22 |
Correct |
7 ms |
1224 KB |
Output is correct |
23 |
Correct |
6 ms |
1180 KB |
Output is correct |
24 |
Correct |
6 ms |
1236 KB |
Output is correct |
25 |
Correct |
6 ms |
1236 KB |
Output is correct |
26 |
Correct |
5 ms |
1232 KB |
Output is correct |
27 |
Correct |
4 ms |
1236 KB |
Output is correct |
28 |
Correct |
5 ms |
1236 KB |
Output is correct |
29 |
Correct |
6 ms |
1304 KB |
Output is correct |
30 |
Correct |
8 ms |
1228 KB |
Output is correct |
31 |
Correct |
7 ms |
1236 KB |
Output is correct |
32 |
Correct |
8 ms |
1236 KB |
Output is correct |
33 |
Correct |
8 ms |
1252 KB |
Output is correct |
34 |
Correct |
9 ms |
1236 KB |
Output is correct |
35 |
Correct |
8 ms |
1236 KB |
Output is correct |
36 |
Correct |
1 ms |
320 KB |
Output is correct |
37 |
Correct |
7 ms |
1236 KB |
Output is correct |
38 |
Correct |
8 ms |
1272 KB |
Output is correct |
39 |
Correct |
7 ms |
1236 KB |
Output is correct |
40 |
Correct |
535 ms |
42628 KB |
Output is correct |
41 |
Correct |
712 ms |
38188 KB |
Output is correct |
42 |
Correct |
667 ms |
39548 KB |
Output is correct |
43 |
Correct |
536 ms |
37948 KB |
Output is correct |
44 |
Correct |
534 ms |
37688 KB |
Output is correct |
45 |
Correct |
813 ms |
47060 KB |
Output is correct |
46 |
Correct |
823 ms |
47052 KB |
Output is correct |
47 |
Correct |
792 ms |
47300 KB |
Output is correct |
48 |
Correct |
810 ms |
47092 KB |
Output is correct |
49 |
Correct |
812 ms |
47192 KB |
Output is correct |
50 |
Correct |
1089 ms |
50908 KB |
Output is correct |
51 |
Correct |
999 ms |
51208 KB |
Output is correct |
52 |
Correct |
1012 ms |
50660 KB |
Output is correct |
53 |
Correct |
943 ms |
47064 KB |
Output is correct |
54 |
Correct |
992 ms |
47128 KB |
Output is correct |
55 |
Correct |
959 ms |
46916 KB |
Output is correct |
56 |
Correct |
768 ms |
47880 KB |
Output is correct |
57 |
Correct |
834 ms |
48080 KB |
Output is correct |
58 |
Correct |
815 ms |
49472 KB |
Output is correct |
59 |
Correct |
806 ms |
47464 KB |
Output is correct |
60 |
Correct |
645 ms |
48068 KB |
Output is correct |
61 |
Correct |
586 ms |
48460 KB |
Output is correct |
62 |
Correct |
632 ms |
48232 KB |
Output is correct |
63 |
Correct |
301 ms |
48488 KB |
Output is correct |
64 |
Correct |
311 ms |
48076 KB |
Output is correct |
65 |
Correct |
424 ms |
47872 KB |
Output is correct |
66 |
Correct |
454 ms |
48044 KB |
Output is correct |
67 |
Correct |
0 ms |
212 KB |
Output is correct |
68 |
Correct |
8 ms |
1236 KB |
Output is correct |
69 |
Correct |
8 ms |
1244 KB |
Output is correct |
70 |
Correct |
8 ms |
1252 KB |
Output is correct |
71 |
Correct |
630 ms |
45100 KB |
Output is correct |
72 |
Correct |
684 ms |
43776 KB |
Output is correct |
73 |
Correct |
752 ms |
34280 KB |
Output is correct |
74 |
Correct |
987 ms |
51236 KB |
Output is correct |
75 |
Correct |
998 ms |
51220 KB |
Output is correct |
76 |
Correct |
1036 ms |
51264 KB |
Output is correct |
77 |
Correct |
793 ms |
51276 KB |
Output is correct |
78 |
Correct |
738 ms |
51276 KB |
Output is correct |
79 |
Correct |
802 ms |
51056 KB |
Output is correct |
80 |
Correct |
473 ms |
50180 KB |
Output is correct |
81 |
Correct |
442 ms |
49888 KB |
Output is correct |
82 |
Correct |
551 ms |
50652 KB |
Output is correct |
83 |
Correct |
520 ms |
50336 KB |
Output is correct |
84 |
Correct |
631 ms |
38024 KB |
Output is correct |
85 |
Correct |
664 ms |
30348 KB |
Output is correct |
86 |
Correct |
573 ms |
28700 KB |
Output is correct |
87 |
Correct |
877 ms |
47172 KB |
Output is correct |
88 |
Correct |
950 ms |
47064 KB |
Output is correct |
89 |
Correct |
950 ms |
46984 KB |
Output is correct |
90 |
Correct |
934 ms |
46828 KB |
Output is correct |
91 |
Correct |
914 ms |
47076 KB |
Output is correct |
92 |
Correct |
1074 ms |
49876 KB |
Output is correct |
93 |
Correct |
1100 ms |
50648 KB |
Output is correct |
94 |
Correct |
1070 ms |
46868 KB |
Output is correct |
95 |
Correct |
1049 ms |
46928 KB |
Output is correct |
96 |
Correct |
1109 ms |
46936 KB |
Output is correct |
97 |
Correct |
1083 ms |
47028 KB |
Output is correct |
98 |
Correct |
861 ms |
48124 KB |
Output is correct |
99 |
Correct |
931 ms |
49424 KB |
Output is correct |
100 |
Correct |
938 ms |
49656 KB |
Output is correct |
101 |
Correct |
869 ms |
47324 KB |
Output is correct |
102 |
Correct |
707 ms |
47624 KB |
Output is correct |
103 |
Correct |
687 ms |
48452 KB |
Output is correct |
104 |
Correct |
709 ms |
48096 KB |
Output is correct |
105 |
Correct |
378 ms |
47248 KB |
Output is correct |
106 |
Correct |
422 ms |
47992 KB |
Output is correct |
107 |
Correct |
488 ms |
47672 KB |
Output is correct |
108 |
Correct |
515 ms |
47912 KB |
Output is correct |