#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;
#define maxn 200005
#define lg 20
int n,m,q;
vector<int> g[maxn];
int in[maxn],out[maxn],st[lg][maxn],ti = 0;
int in2[maxn],out2[maxn],ti2 = 0;
pair<int,int> e[maxn];
vector<pll> v;
void dfs1(int u,int p){
in[u] = ++ti;
in2[u] = ++ti2;
st[0][u] = p;
for(int s : g[u]){
if(s==p) continue;
dfs1(s,u);
}
out[u] = ++ti;
out2[u] = ti2 - 1;
}
bool intree(int x,int y){return in2[y]<=in2[x]&&out2[y]>=out2[x];}
int lca(int x,int y){
if(intree(x,y)) return y;
if(intree(y,x)) return x;
for(int j = lg-1;j>=0;j--){
if(!intree(x,st[j][y])) y = st[j][y];
}
return st[0][y];
}
struct segtree{
ll t[2*maxn];
segtree(){};
void init(int &v,int tl,int tr){
}
ll sum(ll i){
ll ans = 0;
for(; i>=0; i = (i&(i+1))-1) ans+=t[i];
return ans;
}
void upd(int v,int tl,int tr,int i,int x){
for(; i < 2*maxn;i = i|(i+1)) t[i]+=x;
}
ll sum(int v,int tl,int tr,int l,int r){
return sum(r) - sum(l-1);
}
} tsum,tcnt,tg;
vector<ll> Q[maxn];
int L[maxn],R[maxn],MID[maxn];
int sta[maxn],en[maxn];
int au[maxn];
ll ag[maxn];
int ansl[maxn];
int ansr[maxn];
int rez[maxn];
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> m >> q;
for(int i = 1;i<=n-1;i++){
ll x,y; cin >> x >> y;
e[i] = {x,y};
g[x].pb(y);
g[y].pb(x);
}
v.pb({-1,-1});
for(int i = 1;i<=m;i++){
ll j,w; cin >> j >> w;
v.pb({w,j});
}
sort(all(v));
dfs1(1,1);
for(int j = 1;j<lg;j++) for(int i = 1;i<=n;i++) st[j][i] = st[j-1][st[j-1][i]];
for(int i = 1;i<=q;i++) cin >> sta[i] >> en[i] >> au[i] >> ag[i];
for(int i = 1;i<=q;i++){
L[i] = 0,R[i] = m;
ansl[i] = m+1;
ansr[i] = -llinf;
rez[i] = 0;
}
bool change = 1;
while(change){
for(int i = 0;i<=m;i++) Q[i].clear();
change = 0;
for(int i = 1;i<=q;i++){
if(L[i]>R[i]) continue;
change = 1;
MID[i] = (L[i] + R[i])/2;
Q[MID[i]].pb(i);
}
//here;
for(int i = m;i>=0;i--){
if(v[i].fi!=-1){
ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
if(st[0][y]==x) swap(x,y);
ll w = v[i].fi;
tg.upd(1,1,ti,in[x],1);
tg.upd(1,1,ti,out[x],-1);
}
}
//here;
for(int i = 0;i<=m;i++){
if(v[i].fi!=-1){
ll x = e[v[i].sc].fi,y = e[v[i].sc].sc;
if(st[0][y]==x) swap(x,y);
ll w = v[i].fi;
//cerr<<"w: "<<x<< " "<<y<< " "<<w<<endl;
tsum.upd(1,1,ti,in[x],w);
tsum.upd(1,1,ti,out[x],-w);
tcnt.upd(1,1,ti,in[x],1);
tcnt.upd(1,1,ti,out[x],-1);
tg.upd(1,1,ti,in[x],-1);
tg.upd(1,1,ti,out[x],1);
}
for(int j : Q[i]){
int x = sta[j],y = en[j];
int c = au[j];
ll d = ag[j];
int z = lca(x,y);
//cerr<<"LCA: "<<x<< " "<<y<<" "<<z<<endl;
ll cur = 0;
int cntg = 0;
if(z!=x&&z!=y){
cur = tsum.sum(1,1,ti,in[z]+1,in[x]) + tsum.sum(1,1,ti,in[z]+1,in[y]);
cntg = tg.sum(1,1,ti,in[z]+1,in[x]) + tg.sum(1,1,ti,in[z]+1,in[y]);
}else{
if(x==z) swap(x,y);
cur = tsum.sum(1,1,ti,in[z]+1,in[x]);
cntg = tg.sum(1,1,ti,in[z]+1,in[x]);
}
if(cur<=d){
ansr[j] = MID[j];
rez[j] = cntg;
L[j] = MID[j] + 1;
}else R[j] = MID[j] - 1;
//if(j==8) cerr<<"j: "<<x<< " "<<y<< " "<<d<< " "<<cur<<endl;
}
Q[i].clear();
}
for(int i = 0;i<=m;i++){
if(v[i].fi!=-1){
int x = e[v[i].sc].fi,y = e[v[i].sc].sc;
if(st[0][y]==x) swap(x,y);
ll w = v[i].fi;
tsum.upd(1,1,ti,in[x],-w);
tsum.upd(1,1,ti,out[x],w);
tcnt.upd(1,1,ti,in[x],-1);
tcnt.upd(1,1,ti,out[x],1);
}
}
}
for(int i = 1;i<=q;i++){
if(au[i]<rez[i]){
cout<<-1<<endl;
continue;
}else cout<<au[i] - rez[i]<<endl;
}
return 0;
}
/**
5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1
10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3
8 7 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
7 1 5 55
3 1 6 8
8 2 5 45
4 6 4 45
6 1 3 33
2 1 0 19
3 7 2 31
7 1 2 31
7 2 4 58
8 3 5 63
**/
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:95:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '-100000000000000000' to '-1569325056' [-Woverflow]
95 | ansr[i] = -llinf;
| ^
currencies.cpp:113:20: warning: unused variable 'w' [-Wunused-variable]
113 | ll w = v[i].fi;
| ^
currencies.cpp:134:21: warning: unused variable 'c' [-Wunused-variable]
134 | int c = au[j];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
9932 KB |
Output is correct |
2 |
Correct |
6 ms |
9940 KB |
Output is correct |
3 |
Correct |
5 ms |
9940 KB |
Output is correct |
4 |
Correct |
6 ms |
9980 KB |
Output is correct |
5 |
Correct |
19 ms |
10580 KB |
Output is correct |
6 |
Correct |
39 ms |
10736 KB |
Output is correct |
7 |
Correct |
18 ms |
10580 KB |
Output is correct |
8 |
Correct |
23 ms |
10680 KB |
Output is correct |
9 |
Correct |
23 ms |
10708 KB |
Output is correct |
10 |
Correct |
23 ms |
10652 KB |
Output is correct |
11 |
Correct |
24 ms |
10652 KB |
Output is correct |
12 |
Correct |
23 ms |
10712 KB |
Output is correct |
13 |
Correct |
19 ms |
10756 KB |
Output is correct |
14 |
Correct |
19 ms |
10708 KB |
Output is correct |
15 |
Correct |
23 ms |
10708 KB |
Output is correct |
16 |
Correct |
23 ms |
10692 KB |
Output is correct |
17 |
Correct |
23 ms |
10708 KB |
Output is correct |
18 |
Correct |
29 ms |
10776 KB |
Output is correct |
19 |
Correct |
19 ms |
10684 KB |
Output is correct |
20 |
Correct |
21 ms |
10788 KB |
Output is correct |
21 |
Correct |
20 ms |
10680 KB |
Output is correct |
22 |
Correct |
86 ms |
10768 KB |
Output is correct |
23 |
Correct |
28 ms |
10712 KB |
Output is correct |
24 |
Correct |
19 ms |
10676 KB |
Output is correct |
25 |
Correct |
22 ms |
10740 KB |
Output is correct |
26 |
Correct |
18 ms |
10708 KB |
Output is correct |
27 |
Correct |
22 ms |
10724 KB |
Output is correct |
28 |
Correct |
21 ms |
10752 KB |
Output is correct |
29 |
Correct |
24 ms |
10724 KB |
Output is correct |
30 |
Correct |
24 ms |
10648 KB |
Output is correct |
31 |
Correct |
24 ms |
10740 KB |
Output is correct |
32 |
Correct |
23 ms |
10680 KB |
Output is correct |
33 |
Correct |
24 ms |
10740 KB |
Output is correct |
34 |
Correct |
20 ms |
10732 KB |
Output is correct |
35 |
Correct |
19 ms |
10836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9944 KB |
Output is correct |
2 |
Correct |
23 ms |
10688 KB |
Output is correct |
3 |
Correct |
21 ms |
10700 KB |
Output is correct |
4 |
Correct |
22 ms |
10708 KB |
Output is correct |
5 |
Correct |
3539 ms |
42984 KB |
Output is correct |
6 |
Correct |
3693 ms |
44512 KB |
Output is correct |
7 |
Correct |
3408 ms |
45444 KB |
Output is correct |
8 |
Correct |
2433 ms |
40628 KB |
Output is correct |
9 |
Correct |
2320 ms |
39952 KB |
Output is correct |
10 |
Correct |
4241 ms |
52160 KB |
Output is correct |
11 |
Correct |
4197 ms |
56212 KB |
Output is correct |
12 |
Correct |
4998 ms |
55856 KB |
Output is correct |
13 |
Correct |
4094 ms |
56192 KB |
Output is correct |
14 |
Correct |
4323 ms |
56148 KB |
Output is correct |
15 |
Correct |
1770 ms |
60576 KB |
Output is correct |
16 |
Correct |
1527 ms |
60824 KB |
Output is correct |
17 |
Correct |
2081 ms |
60388 KB |
Output is correct |
18 |
Correct |
3968 ms |
56452 KB |
Output is correct |
19 |
Correct |
4046 ms |
56360 KB |
Output is correct |
20 |
Correct |
3952 ms |
56352 KB |
Output is correct |
21 |
Correct |
3142 ms |
57384 KB |
Output is correct |
22 |
Correct |
3172 ms |
57296 KB |
Output is correct |
23 |
Correct |
3390 ms |
57400 KB |
Output is correct |
24 |
Correct |
3211 ms |
57280 KB |
Output is correct |
25 |
Correct |
2502 ms |
55568 KB |
Output is correct |
26 |
Correct |
2686 ms |
55316 KB |
Output is correct |
27 |
Correct |
2573 ms |
55576 KB |
Output is correct |
28 |
Correct |
1159 ms |
54772 KB |
Output is correct |
29 |
Correct |
1223 ms |
53764 KB |
Output is correct |
30 |
Correct |
1685 ms |
53676 KB |
Output is correct |
31 |
Correct |
1508 ms |
53792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
10068 KB |
Output is correct |
2 |
Correct |
18 ms |
10804 KB |
Output is correct |
3 |
Correct |
18 ms |
10836 KB |
Output is correct |
4 |
Correct |
17 ms |
10836 KB |
Output is correct |
5 |
Correct |
933 ms |
46780 KB |
Output is correct |
6 |
Correct |
772 ms |
46272 KB |
Output is correct |
7 |
Correct |
1082 ms |
42668 KB |
Output is correct |
8 |
Correct |
1588 ms |
56952 KB |
Output is correct |
9 |
Correct |
1691 ms |
56984 KB |
Output is correct |
10 |
Correct |
1699 ms |
57028 KB |
Output is correct |
11 |
Correct |
1371 ms |
57080 KB |
Output is correct |
12 |
Correct |
1203 ms |
56956 KB |
Output is correct |
13 |
Correct |
1271 ms |
56980 KB |
Output is correct |
14 |
Correct |
1407 ms |
56768 KB |
Output is correct |
15 |
Correct |
1459 ms |
56804 KB |
Output is correct |
16 |
Correct |
1737 ms |
56876 KB |
Output is correct |
17 |
Correct |
1504 ms |
56780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
9932 KB |
Output is correct |
2 |
Correct |
6 ms |
9940 KB |
Output is correct |
3 |
Correct |
5 ms |
9940 KB |
Output is correct |
4 |
Correct |
6 ms |
9980 KB |
Output is correct |
5 |
Correct |
19 ms |
10580 KB |
Output is correct |
6 |
Correct |
39 ms |
10736 KB |
Output is correct |
7 |
Correct |
18 ms |
10580 KB |
Output is correct |
8 |
Correct |
23 ms |
10680 KB |
Output is correct |
9 |
Correct |
23 ms |
10708 KB |
Output is correct |
10 |
Correct |
23 ms |
10652 KB |
Output is correct |
11 |
Correct |
24 ms |
10652 KB |
Output is correct |
12 |
Correct |
23 ms |
10712 KB |
Output is correct |
13 |
Correct |
19 ms |
10756 KB |
Output is correct |
14 |
Correct |
19 ms |
10708 KB |
Output is correct |
15 |
Correct |
23 ms |
10708 KB |
Output is correct |
16 |
Correct |
23 ms |
10692 KB |
Output is correct |
17 |
Correct |
23 ms |
10708 KB |
Output is correct |
18 |
Correct |
29 ms |
10776 KB |
Output is correct |
19 |
Correct |
19 ms |
10684 KB |
Output is correct |
20 |
Correct |
21 ms |
10788 KB |
Output is correct |
21 |
Correct |
20 ms |
10680 KB |
Output is correct |
22 |
Correct |
86 ms |
10768 KB |
Output is correct |
23 |
Correct |
28 ms |
10712 KB |
Output is correct |
24 |
Correct |
19 ms |
10676 KB |
Output is correct |
25 |
Correct |
22 ms |
10740 KB |
Output is correct |
26 |
Correct |
18 ms |
10708 KB |
Output is correct |
27 |
Correct |
22 ms |
10724 KB |
Output is correct |
28 |
Correct |
21 ms |
10752 KB |
Output is correct |
29 |
Correct |
24 ms |
10724 KB |
Output is correct |
30 |
Correct |
24 ms |
10648 KB |
Output is correct |
31 |
Correct |
24 ms |
10740 KB |
Output is correct |
32 |
Correct |
23 ms |
10680 KB |
Output is correct |
33 |
Correct |
24 ms |
10740 KB |
Output is correct |
34 |
Correct |
20 ms |
10732 KB |
Output is correct |
35 |
Correct |
19 ms |
10836 KB |
Output is correct |
36 |
Correct |
6 ms |
9944 KB |
Output is correct |
37 |
Correct |
23 ms |
10688 KB |
Output is correct |
38 |
Correct |
21 ms |
10700 KB |
Output is correct |
39 |
Correct |
22 ms |
10708 KB |
Output is correct |
40 |
Correct |
3539 ms |
42984 KB |
Output is correct |
41 |
Correct |
3693 ms |
44512 KB |
Output is correct |
42 |
Correct |
3408 ms |
45444 KB |
Output is correct |
43 |
Correct |
2433 ms |
40628 KB |
Output is correct |
44 |
Correct |
2320 ms |
39952 KB |
Output is correct |
45 |
Correct |
4241 ms |
52160 KB |
Output is correct |
46 |
Correct |
4197 ms |
56212 KB |
Output is correct |
47 |
Correct |
4998 ms |
55856 KB |
Output is correct |
48 |
Correct |
4094 ms |
56192 KB |
Output is correct |
49 |
Correct |
4323 ms |
56148 KB |
Output is correct |
50 |
Correct |
1770 ms |
60576 KB |
Output is correct |
51 |
Correct |
1527 ms |
60824 KB |
Output is correct |
52 |
Correct |
2081 ms |
60388 KB |
Output is correct |
53 |
Correct |
3968 ms |
56452 KB |
Output is correct |
54 |
Correct |
4046 ms |
56360 KB |
Output is correct |
55 |
Correct |
3952 ms |
56352 KB |
Output is correct |
56 |
Correct |
3142 ms |
57384 KB |
Output is correct |
57 |
Correct |
3172 ms |
57296 KB |
Output is correct |
58 |
Correct |
3390 ms |
57400 KB |
Output is correct |
59 |
Correct |
3211 ms |
57280 KB |
Output is correct |
60 |
Correct |
2502 ms |
55568 KB |
Output is correct |
61 |
Correct |
2686 ms |
55316 KB |
Output is correct |
62 |
Correct |
2573 ms |
55576 KB |
Output is correct |
63 |
Correct |
1159 ms |
54772 KB |
Output is correct |
64 |
Correct |
1223 ms |
53764 KB |
Output is correct |
65 |
Correct |
1685 ms |
53676 KB |
Output is correct |
66 |
Correct |
1508 ms |
53792 KB |
Output is correct |
67 |
Correct |
6 ms |
10068 KB |
Output is correct |
68 |
Correct |
18 ms |
10804 KB |
Output is correct |
69 |
Correct |
18 ms |
10836 KB |
Output is correct |
70 |
Correct |
17 ms |
10836 KB |
Output is correct |
71 |
Correct |
933 ms |
46780 KB |
Output is correct |
72 |
Correct |
772 ms |
46272 KB |
Output is correct |
73 |
Correct |
1082 ms |
42668 KB |
Output is correct |
74 |
Correct |
1588 ms |
56952 KB |
Output is correct |
75 |
Correct |
1691 ms |
56984 KB |
Output is correct |
76 |
Correct |
1699 ms |
57028 KB |
Output is correct |
77 |
Correct |
1371 ms |
57080 KB |
Output is correct |
78 |
Correct |
1203 ms |
56956 KB |
Output is correct |
79 |
Correct |
1271 ms |
56980 KB |
Output is correct |
80 |
Correct |
1407 ms |
56768 KB |
Output is correct |
81 |
Correct |
1459 ms |
56804 KB |
Output is correct |
82 |
Correct |
1737 ms |
56876 KB |
Output is correct |
83 |
Correct |
1504 ms |
56780 KB |
Output is correct |
84 |
Correct |
2669 ms |
45032 KB |
Output is correct |
85 |
Correct |
2193 ms |
41968 KB |
Output is correct |
86 |
Correct |
2202 ms |
40756 KB |
Output is correct |
87 |
Correct |
4549 ms |
57200 KB |
Output is correct |
88 |
Correct |
4228 ms |
56624 KB |
Output is correct |
89 |
Correct |
4472 ms |
57228 KB |
Output is correct |
90 |
Correct |
4532 ms |
57508 KB |
Output is correct |
91 |
Correct |
4334 ms |
57416 KB |
Output is correct |
92 |
Correct |
2945 ms |
61008 KB |
Output is correct |
93 |
Correct |
2374 ms |
61888 KB |
Output is correct |
94 |
Correct |
4302 ms |
57756 KB |
Output is correct |
95 |
Correct |
4615 ms |
57952 KB |
Output is correct |
96 |
Correct |
4795 ms |
57708 KB |
Output is correct |
97 |
Correct |
4111 ms |
57960 KB |
Output is correct |
98 |
Correct |
3992 ms |
57736 KB |
Output is correct |
99 |
Correct |
4132 ms |
57344 KB |
Output is correct |
100 |
Correct |
3952 ms |
57508 KB |
Output is correct |
101 |
Correct |
3700 ms |
57836 KB |
Output is correct |
102 |
Correct |
2748 ms |
57776 KB |
Output is correct |
103 |
Correct |
2668 ms |
57968 KB |
Output is correct |
104 |
Correct |
2902 ms |
57980 KB |
Output is correct |
105 |
Correct |
1461 ms |
54536 KB |
Output is correct |
106 |
Correct |
1376 ms |
55860 KB |
Output is correct |
107 |
Correct |
1783 ms |
54452 KB |
Output is correct |
108 |
Correct |
1761 ms |
54488 KB |
Output is correct |