#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cerr<<#x << " : " << x << "\n";
using namespace std ;
const int maxn = 1e5 + 10 , mod = 1e9 + 7 , inf =1e9 , lg = 19 ;
int fen[maxn],par[maxn][lg+1],dis[maxn],pai[maxn],l[maxn],r[maxn],x[maxn],y[maxn],V[maxn],U[maxn],st[maxn],en[maxn];
int cnt=1, n , m , q,ans[maxn];
vector <int> vec[maxn] ;
vector <pii> ed, G[maxn];
void upd(int x, int w){
while(x<=n){
fen[x] += w;
x+=x&-x;
}
}
int que(int v){
int ans =0 ;
while(v){
ans += fen[v] ;
v-=v&-v ;
}
return ans ;
}
int up(int v ,int d){
rep(i ,0,lg)if(d>>i&1)v= par[v][i] ;
return v ;
}
int lca(int v,int u){
if(dis[v] < dis[u])swap(v,u);
v=up(v,dis[v]-dis[u]);
per(i , lg ,0 ){
if(par[v][i]!=par[u][i])v = par[v][i] , u = par[u][i] ;
}
if(v==u)return v;
return par[v][0] ;
}
void d1(int v, int p =0){
par[v][0] = p;
rep(i , 1,lg){
par[v][i] = par[par[v][i-1]][i-1] ;
}
st[v] = cnt ;cnt++;
for(pii u : G[v]){
if(u.F == p)continue ;
pai[u.S] = u.F ;
dis[u.F] = dis[v]+1 ;
d1(u.F , v) ;
}
en[v] = cnt-1 ;
}
signed main(){
ios::sync_with_stdio(0) ;cin.tie(0);
cin >> n >> m >> q;
rep(i , 1 , n-1){
int v,u ;
cin >> v >> u ;
G[v].pb({u ,i});
G[u].pb({v,i}) ;
}
d1(1);
rep(i , 1, m){
int id , w ;
cin >> id >> w ;
ed.pb({w,id}) ;
}
sort(all(ed));
rep(i , 1, q){
cin >> V[i] >> U[i] >> x[i] >> y[i] ;
l[i] = -1 ;
r[i] =sz(ed) ;
}
rep(i , 0 , lg){
rep(i , 1,q){
vec[(l[i]+r[i])/2].pb(i);
}
rep(i , 0 , sz(ed)-1){
int v =pai[ed[i].S] , w = ed[i].F ;
upd(st[v] , w);upd(en[v]+1,-w);
for(int id : vec[i]){
if(que(st[V[id]]) + que(st[U[id]]) - 2*que(st[lca(V[id] , U[id])]) <= y[id]){
l[id] = i ;
}else{
r[id] = i ;
}
}
}
rep(j , 0 , max(n , sz(ed))){
fen[j] =0 ;
vec[j].clear() ;
}
}
rep(i , 1 , q){
vec[l[i]+1].pb(i) ;
}
per(i , sz(ed) , 0){
for(int id : vec[i]){
ans[id] = que(st[V[id]]) + que(st[U[id]]) - 2*que(st[lca(V[id] , U[id])]) ;
}
if(i ==0 )continue ;
int v=pai[ed[i-1].S] , w = ed[i-1].F ;
upd(st[v] , 1) ; upd(en[v]+1, -1) ;
}
rep(i , 1, q){
if(ans[i] > x[i]){
cout << "-1\n";
}else{
cout << x[i]-ans[i] << "\n";
}
}
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:116:32: warning: unused variable 'w' [-Wunused-variable]
116 | int v=pai[ed[i-1].S] , w = ed[i-1].F ;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14936 KB |
Output is correct |
3 |
Correct |
4 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14988 KB |
Output is correct |
5 |
Correct |
8 ms |
15196 KB |
Output is correct |
6 |
Correct |
10 ms |
15452 KB |
Output is correct |
7 |
Correct |
9 ms |
15360 KB |
Output is correct |
8 |
Correct |
11 ms |
15452 KB |
Output is correct |
9 |
Correct |
12 ms |
15452 KB |
Output is correct |
10 |
Correct |
11 ms |
15480 KB |
Output is correct |
11 |
Correct |
14 ms |
15624 KB |
Output is correct |
12 |
Correct |
11 ms |
15508 KB |
Output is correct |
13 |
Correct |
12 ms |
15448 KB |
Output is correct |
14 |
Correct |
14 ms |
15452 KB |
Output is correct |
15 |
Correct |
12 ms |
15452 KB |
Output is correct |
16 |
Correct |
12 ms |
15452 KB |
Output is correct |
17 |
Correct |
12 ms |
15452 KB |
Output is correct |
18 |
Correct |
12 ms |
15448 KB |
Output is correct |
19 |
Correct |
9 ms |
15452 KB |
Output is correct |
20 |
Correct |
9 ms |
15452 KB |
Output is correct |
21 |
Correct |
9 ms |
15452 KB |
Output is correct |
22 |
Correct |
9 ms |
15452 KB |
Output is correct |
23 |
Correct |
10 ms |
15452 KB |
Output is correct |
24 |
Correct |
10 ms |
15452 KB |
Output is correct |
25 |
Correct |
9 ms |
15452 KB |
Output is correct |
26 |
Correct |
9 ms |
15448 KB |
Output is correct |
27 |
Correct |
8 ms |
15452 KB |
Output is correct |
28 |
Correct |
8 ms |
15456 KB |
Output is correct |
29 |
Correct |
8 ms |
15452 KB |
Output is correct |
30 |
Correct |
12 ms |
15452 KB |
Output is correct |
31 |
Correct |
11 ms |
15452 KB |
Output is correct |
32 |
Correct |
11 ms |
15452 KB |
Output is correct |
33 |
Correct |
11 ms |
15452 KB |
Output is correct |
34 |
Correct |
11 ms |
15436 KB |
Output is correct |
35 |
Correct |
12 ms |
15448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14940 KB |
Output is correct |
2 |
Correct |
11 ms |
15500 KB |
Output is correct |
3 |
Correct |
10 ms |
15452 KB |
Output is correct |
4 |
Correct |
10 ms |
15452 KB |
Output is correct |
5 |
Correct |
707 ms |
52324 KB |
Output is correct |
6 |
Correct |
849 ms |
53016 KB |
Output is correct |
7 |
Correct |
917 ms |
53932 KB |
Output is correct |
8 |
Correct |
645 ms |
48956 KB |
Output is correct |
9 |
Correct |
689 ms |
48624 KB |
Output is correct |
10 |
Correct |
1218 ms |
60452 KB |
Output is correct |
11 |
Correct |
1070 ms |
60444 KB |
Output is correct |
12 |
Correct |
1190 ms |
60264 KB |
Output is correct |
13 |
Correct |
1210 ms |
60272 KB |
Output is correct |
14 |
Correct |
1195 ms |
60500 KB |
Output is correct |
15 |
Correct |
2524 ms |
67872 KB |
Output is correct |
16 |
Correct |
2576 ms |
68512 KB |
Output is correct |
17 |
Correct |
3055 ms |
67488 KB |
Output is correct |
18 |
Correct |
2056 ms |
60712 KB |
Output is correct |
19 |
Correct |
2168 ms |
60704 KB |
Output is correct |
20 |
Correct |
2262 ms |
60812 KB |
Output is correct |
21 |
Correct |
1035 ms |
60484 KB |
Output is correct |
22 |
Correct |
963 ms |
60732 KB |
Output is correct |
23 |
Correct |
933 ms |
60732 KB |
Output is correct |
24 |
Correct |
990 ms |
60576 KB |
Output is correct |
25 |
Correct |
807 ms |
59876 KB |
Output is correct |
26 |
Correct |
860 ms |
59868 KB |
Output is correct |
27 |
Correct |
830 ms |
60116 KB |
Output is correct |
28 |
Correct |
398 ms |
58760 KB |
Output is correct |
29 |
Correct |
312 ms |
57692 KB |
Output is correct |
30 |
Correct |
437 ms |
58052 KB |
Output is correct |
31 |
Correct |
508 ms |
57796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
12 ms |
15668 KB |
Output is correct |
3 |
Correct |
11 ms |
15448 KB |
Output is correct |
4 |
Correct |
11 ms |
15452 KB |
Output is correct |
5 |
Correct |
1300 ms |
59076 KB |
Output is correct |
6 |
Correct |
1287 ms |
58620 KB |
Output is correct |
7 |
Correct |
930 ms |
52892 KB |
Output is correct |
8 |
Correct |
2362 ms |
68284 KB |
Output is correct |
9 |
Correct |
2386 ms |
68304 KB |
Output is correct |
10 |
Correct |
2589 ms |
68272 KB |
Output is correct |
11 |
Correct |
1165 ms |
68476 KB |
Output is correct |
12 |
Correct |
1128 ms |
68212 KB |
Output is correct |
13 |
Correct |
1102 ms |
68328 KB |
Output is correct |
14 |
Correct |
352 ms |
68156 KB |
Output is correct |
15 |
Correct |
329 ms |
68096 KB |
Output is correct |
16 |
Correct |
676 ms |
68568 KB |
Output is correct |
17 |
Correct |
619 ms |
68236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14936 KB |
Output is correct |
3 |
Correct |
4 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14988 KB |
Output is correct |
5 |
Correct |
8 ms |
15196 KB |
Output is correct |
6 |
Correct |
10 ms |
15452 KB |
Output is correct |
7 |
Correct |
9 ms |
15360 KB |
Output is correct |
8 |
Correct |
11 ms |
15452 KB |
Output is correct |
9 |
Correct |
12 ms |
15452 KB |
Output is correct |
10 |
Correct |
11 ms |
15480 KB |
Output is correct |
11 |
Correct |
14 ms |
15624 KB |
Output is correct |
12 |
Correct |
11 ms |
15508 KB |
Output is correct |
13 |
Correct |
12 ms |
15448 KB |
Output is correct |
14 |
Correct |
14 ms |
15452 KB |
Output is correct |
15 |
Correct |
12 ms |
15452 KB |
Output is correct |
16 |
Correct |
12 ms |
15452 KB |
Output is correct |
17 |
Correct |
12 ms |
15452 KB |
Output is correct |
18 |
Correct |
12 ms |
15448 KB |
Output is correct |
19 |
Correct |
9 ms |
15452 KB |
Output is correct |
20 |
Correct |
9 ms |
15452 KB |
Output is correct |
21 |
Correct |
9 ms |
15452 KB |
Output is correct |
22 |
Correct |
9 ms |
15452 KB |
Output is correct |
23 |
Correct |
10 ms |
15452 KB |
Output is correct |
24 |
Correct |
10 ms |
15452 KB |
Output is correct |
25 |
Correct |
9 ms |
15452 KB |
Output is correct |
26 |
Correct |
9 ms |
15448 KB |
Output is correct |
27 |
Correct |
8 ms |
15452 KB |
Output is correct |
28 |
Correct |
8 ms |
15456 KB |
Output is correct |
29 |
Correct |
8 ms |
15452 KB |
Output is correct |
30 |
Correct |
12 ms |
15452 KB |
Output is correct |
31 |
Correct |
11 ms |
15452 KB |
Output is correct |
32 |
Correct |
11 ms |
15452 KB |
Output is correct |
33 |
Correct |
11 ms |
15452 KB |
Output is correct |
34 |
Correct |
11 ms |
15436 KB |
Output is correct |
35 |
Correct |
12 ms |
15448 KB |
Output is correct |
36 |
Correct |
4 ms |
14940 KB |
Output is correct |
37 |
Correct |
11 ms |
15500 KB |
Output is correct |
38 |
Correct |
10 ms |
15452 KB |
Output is correct |
39 |
Correct |
10 ms |
15452 KB |
Output is correct |
40 |
Correct |
707 ms |
52324 KB |
Output is correct |
41 |
Correct |
849 ms |
53016 KB |
Output is correct |
42 |
Correct |
917 ms |
53932 KB |
Output is correct |
43 |
Correct |
645 ms |
48956 KB |
Output is correct |
44 |
Correct |
689 ms |
48624 KB |
Output is correct |
45 |
Correct |
1218 ms |
60452 KB |
Output is correct |
46 |
Correct |
1070 ms |
60444 KB |
Output is correct |
47 |
Correct |
1190 ms |
60264 KB |
Output is correct |
48 |
Correct |
1210 ms |
60272 KB |
Output is correct |
49 |
Correct |
1195 ms |
60500 KB |
Output is correct |
50 |
Correct |
2524 ms |
67872 KB |
Output is correct |
51 |
Correct |
2576 ms |
68512 KB |
Output is correct |
52 |
Correct |
3055 ms |
67488 KB |
Output is correct |
53 |
Correct |
2056 ms |
60712 KB |
Output is correct |
54 |
Correct |
2168 ms |
60704 KB |
Output is correct |
55 |
Correct |
2262 ms |
60812 KB |
Output is correct |
56 |
Correct |
1035 ms |
60484 KB |
Output is correct |
57 |
Correct |
963 ms |
60732 KB |
Output is correct |
58 |
Correct |
933 ms |
60732 KB |
Output is correct |
59 |
Correct |
990 ms |
60576 KB |
Output is correct |
60 |
Correct |
807 ms |
59876 KB |
Output is correct |
61 |
Correct |
860 ms |
59868 KB |
Output is correct |
62 |
Correct |
830 ms |
60116 KB |
Output is correct |
63 |
Correct |
398 ms |
58760 KB |
Output is correct |
64 |
Correct |
312 ms |
57692 KB |
Output is correct |
65 |
Correct |
437 ms |
58052 KB |
Output is correct |
66 |
Correct |
508 ms |
57796 KB |
Output is correct |
67 |
Correct |
3 ms |
14940 KB |
Output is correct |
68 |
Correct |
12 ms |
15668 KB |
Output is correct |
69 |
Correct |
11 ms |
15448 KB |
Output is correct |
70 |
Correct |
11 ms |
15452 KB |
Output is correct |
71 |
Correct |
1300 ms |
59076 KB |
Output is correct |
72 |
Correct |
1287 ms |
58620 KB |
Output is correct |
73 |
Correct |
930 ms |
52892 KB |
Output is correct |
74 |
Correct |
2362 ms |
68284 KB |
Output is correct |
75 |
Correct |
2386 ms |
68304 KB |
Output is correct |
76 |
Correct |
2589 ms |
68272 KB |
Output is correct |
77 |
Correct |
1165 ms |
68476 KB |
Output is correct |
78 |
Correct |
1128 ms |
68212 KB |
Output is correct |
79 |
Correct |
1102 ms |
68328 KB |
Output is correct |
80 |
Correct |
352 ms |
68156 KB |
Output is correct |
81 |
Correct |
329 ms |
68096 KB |
Output is correct |
82 |
Correct |
676 ms |
68568 KB |
Output is correct |
83 |
Correct |
619 ms |
68236 KB |
Output is correct |
84 |
Correct |
680 ms |
49856 KB |
Output is correct |
85 |
Correct |
572 ms |
45924 KB |
Output is correct |
86 |
Correct |
547 ms |
44580 KB |
Output is correct |
87 |
Correct |
1230 ms |
60228 KB |
Output is correct |
88 |
Correct |
1248 ms |
60320 KB |
Output is correct |
89 |
Correct |
1250 ms |
60276 KB |
Output is correct |
90 |
Correct |
1218 ms |
60412 KB |
Output is correct |
91 |
Correct |
1262 ms |
60392 KB |
Output is correct |
92 |
Correct |
2821 ms |
66252 KB |
Output is correct |
93 |
Correct |
2753 ms |
67216 KB |
Output is correct |
94 |
Correct |
2205 ms |
60504 KB |
Output is correct |
95 |
Correct |
2201 ms |
60608 KB |
Output is correct |
96 |
Correct |
2234 ms |
60740 KB |
Output is correct |
97 |
Correct |
2245 ms |
61048 KB |
Output is correct |
98 |
Correct |
1089 ms |
60476 KB |
Output is correct |
99 |
Correct |
1061 ms |
59964 KB |
Output is correct |
100 |
Correct |
1066 ms |
60360 KB |
Output is correct |
101 |
Correct |
1089 ms |
60724 KB |
Output is correct |
102 |
Correct |
1030 ms |
60712 KB |
Output is correct |
103 |
Correct |
1057 ms |
60868 KB |
Output is correct |
104 |
Correct |
1026 ms |
60908 KB |
Output is correct |
105 |
Correct |
381 ms |
57472 KB |
Output is correct |
106 |
Correct |
432 ms |
58700 KB |
Output is correct |
107 |
Correct |
465 ms |
57536 KB |
Output is correct |
108 |
Correct |
481 ms |
57260 KB |
Output is correct |