#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXNODE = 2e7+5;
int lf[MAXNODE],rg[MAXNODE],cnt[MAXNODE],ndcnt = 0;
ll sum[MAXNODE];
int new_node(){
ndcnt++;
return ndcnt;
}
int new_node(int v){
ndcnt++;
sum[ndcnt] = sum[v];
cnt[ndcnt] = cnt[v];
lf[ndcnt] = lf[v];
rg[ndcnt] = rg[v];
return ndcnt;
}
//get the double euler tour array
//set cost(i) at tin(i) and -cost(i) at tout(i)
int upd(int v,int pos,int l,int r,ll val){
int u = new_node(v);
if(l==r){
sum[u]+=val;
if(val>0)cnt[u]++;
if(val<0)cnt[u]--;
return u;
}
int tm = (l+r)/2;
if(pos<=tm){
if(!lf[v])lf[v] = new_node();
lf[u] = upd(lf[v],pos,l,tm,val);
}else{
if(!rg[v])rg[v] = new_node();
rg[u] = upd(rg[v],pos,tm+1,r,val);
}
sum[u] = cnt[u] = 0;
if(lf[u]){
sum[u]+=sum[lf[u]];
cnt[u]+=cnt[lf[u]];
}
if(rg[u]){
sum[u]+=sum[rg[u]];
cnt[u]+=cnt[rg[u]];
}
return u;
}
ll query(int v,int l,int r,int tl,int tr){
if(l==tl && r==tr)return sum[v];
int tm = (tl+tr)/2;
if(!lf[v])lf[v] = new_node();
if(!rg[v])rg[v] = new_node();
if(r<=tm)return query(lf[v],l,r,tl,tm);
else if(l>tm)return query(rg[v],l,r,tm+1,tr);
else{
return query(lf[v],l,tm,tl,tm)+query(rg[v],tm+1,r,tm+1,tr);
}
}
ll query2(int v,int l,int r,int tl,int tr){
if(l==tl && r==tr)return cnt[v];
int tm = (tl+tr)/2;
if(!lf[v])lf[v] = new_node();
if(!rg[v])rg[v] = new_node();
if(r<=tm)return query2(lf[v],l,r,tl,tm);
else if(l>tm)return query2(rg[v],l,r,tm+1,tr);
else{
return query2(lf[v],l,tm,tl,tm)+query2(rg[v],tm+1,r,tm+1,tr);
}
}
///////persistent seg
const int MAXN = 5e5+5;
vector<int>adj[MAXN];
int tin[MAXN],tout[MAXN],dep[MAXN],par[19][MAXN],timer = 0;
int cost[MAXN],ett[2*MAXN];
void dfs(int v,int u){
tin[v] = ++timer;
ett[tin[v]] = v;
for(int x:adj[v]){
if(x == u)continue;
par[0][x] = v;
dep[x] = dep[v]+1;
for(int i=1;i<=18;i++){
par[i][x] = par[i-1][par[i-1][x]];
}
dfs(x,v);
}
tout[v] = ++timer;
ett[tout[v]] = -v;
}
bool ancestor(int v,int u){return(tin[v] >= tin[u] && tout[u] >= tout[v]);}//is u an ancestor of v?
int lca(int v,int u){
if(dep[v] > dep[u])swap(u,v);
int dist = dep[u]-dep[v];
for(int i=0;dist;i++,dist>>=1){
if(dist&1)u = par[i][u];
}
if(u == v)return u;
for(int i=18;i>=0;i--){
if(par[i][v] != par[i][u]){
u = par[i][u];
v = par[i][v];
}
}
return par[0][v];
}
int main()
{
owo
int n,m,q;
cin>>n>>m>>q;
vector<pii>ed(n),C(m);
for(int i=1;i<n;i++)cin>>ed[i].fi>>ed[i].se;
for(int i=0;i<m;i++)cin>>C[i].se>>C[i].fi;
vii p(n);
sort(all(C));
int N = n;
for(int i=0;i<m;i++){
N++; //label this guy as N
p[C[i].se].pb(N);
cost[N] = C[i].fi;
}
for(int i=1;i<n;i++){
int a = ed[i].fi;
int b = ed[i].se;
for(int x:p[i]){
adj[a].pb(x);
adj[x].pb(a);
a = x;
}
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1,-1);
vector<int>root(2*N+1);
for(int i=1;i<=2*N;i++){
root[i] = new_node(root[i-1]);
int v = abs(ett[i]);
if(v > n){
if(ett[i]>0)root[i] = upd(root[i],v,1,N,cost[v]);
else root[i] = upd(root[i],v,1,N,-cost[v]);
}
}
while(q--){
int s,t,x;
ll y;
cin>>s>>t>>x>>y;
int v = lca(s,t);
int l = 1,r = N;
//cout<<s<<" "<<t<<" "<<v<<'\n';
while(r>=l){
int tm = (l+r)/2;
ll a = query(root[tin[v]],1,tm,1,N);
ll b = query(root[tin[s]],1,tm,1,N);
ll c = query(root[tin[t]],1,tm,1,N);
if(b+c-2*a > y)r = tm-1;
else l = tm+1;
}
int gol = cnt[root[tin[s]]] + cnt[root[tin[t]]] - 2*cnt[root[tin[v]]];
gol -= query2(root[tin[s]],1,r,1,N) + query2(root[tin[t]],1,r,1,N);
gol += 2*query2(root[tin[v]],1,r,1,N);
if(x>=gol)cout<<x-gol<<'\n';
else cout<<-1<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12244 KB |
Output is correct |
2 |
Correct |
8 ms |
12272 KB |
Output is correct |
3 |
Correct |
6 ms |
12244 KB |
Output is correct |
4 |
Correct |
6 ms |
12244 KB |
Output is correct |
5 |
Correct |
13 ms |
14112 KB |
Output is correct |
6 |
Correct |
13 ms |
14036 KB |
Output is correct |
7 |
Correct |
15 ms |
13572 KB |
Output is correct |
8 |
Correct |
13 ms |
14292 KB |
Output is correct |
9 |
Correct |
14 ms |
14276 KB |
Output is correct |
10 |
Correct |
13 ms |
14192 KB |
Output is correct |
11 |
Correct |
13 ms |
14164 KB |
Output is correct |
12 |
Correct |
13 ms |
14248 KB |
Output is correct |
13 |
Correct |
13 ms |
14540 KB |
Output is correct |
14 |
Correct |
13 ms |
14464 KB |
Output is correct |
15 |
Correct |
13 ms |
14292 KB |
Output is correct |
16 |
Correct |
15 ms |
14356 KB |
Output is correct |
17 |
Correct |
14 ms |
14292 KB |
Output is correct |
18 |
Correct |
16 ms |
14292 KB |
Output is correct |
19 |
Correct |
13 ms |
14204 KB |
Output is correct |
20 |
Correct |
13 ms |
14284 KB |
Output is correct |
21 |
Correct |
14 ms |
14292 KB |
Output is correct |
22 |
Correct |
17 ms |
14292 KB |
Output is correct |
23 |
Correct |
14 ms |
14288 KB |
Output is correct |
24 |
Correct |
15 ms |
14352 KB |
Output is correct |
25 |
Correct |
16 ms |
14292 KB |
Output is correct |
26 |
Correct |
14 ms |
14156 KB |
Output is correct |
27 |
Correct |
12 ms |
14164 KB |
Output is correct |
28 |
Correct |
12 ms |
14180 KB |
Output is correct |
29 |
Correct |
11 ms |
14156 KB |
Output is correct |
30 |
Correct |
13 ms |
14196 KB |
Output is correct |
31 |
Correct |
13 ms |
14292 KB |
Output is correct |
32 |
Correct |
13 ms |
14236 KB |
Output is correct |
33 |
Correct |
13 ms |
14544 KB |
Output is correct |
34 |
Correct |
17 ms |
14568 KB |
Output is correct |
35 |
Correct |
13 ms |
14548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12244 KB |
Output is correct |
2 |
Correct |
13 ms |
14292 KB |
Output is correct |
3 |
Correct |
17 ms |
14280 KB |
Output is correct |
4 |
Correct |
14 ms |
14236 KB |
Output is correct |
5 |
Correct |
975 ms |
123148 KB |
Output is correct |
6 |
Correct |
1410 ms |
110388 KB |
Output is correct |
7 |
Correct |
1226 ms |
95440 KB |
Output is correct |
8 |
Correct |
951 ms |
93932 KB |
Output is correct |
9 |
Correct |
878 ms |
97864 KB |
Output is correct |
10 |
Correct |
1628 ms |
134840 KB |
Output is correct |
11 |
Correct |
1580 ms |
134864 KB |
Output is correct |
12 |
Correct |
1593 ms |
134540 KB |
Output is correct |
13 |
Correct |
1550 ms |
134548 KB |
Output is correct |
14 |
Correct |
1679 ms |
134944 KB |
Output is correct |
15 |
Correct |
1737 ms |
149836 KB |
Output is correct |
16 |
Correct |
1608 ms |
150364 KB |
Output is correct |
17 |
Correct |
1642 ms |
149576 KB |
Output is correct |
18 |
Correct |
1862 ms |
135588 KB |
Output is correct |
19 |
Correct |
1790 ms |
135464 KB |
Output is correct |
20 |
Correct |
1851 ms |
135704 KB |
Output is correct |
21 |
Correct |
924 ms |
182720 KB |
Output is correct |
22 |
Correct |
918 ms |
166808 KB |
Output is correct |
23 |
Correct |
1075 ms |
151420 KB |
Output is correct |
24 |
Correct |
990 ms |
151080 KB |
Output is correct |
25 |
Correct |
1371 ms |
169208 KB |
Output is correct |
26 |
Correct |
1352 ms |
163396 KB |
Output is correct |
27 |
Correct |
1410 ms |
145692 KB |
Output is correct |
28 |
Correct |
744 ms |
135528 KB |
Output is correct |
29 |
Correct |
644 ms |
135448 KB |
Output is correct |
30 |
Correct |
894 ms |
136676 KB |
Output is correct |
31 |
Correct |
918 ms |
137032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12244 KB |
Output is correct |
2 |
Correct |
13 ms |
14548 KB |
Output is correct |
3 |
Correct |
14 ms |
14656 KB |
Output is correct |
4 |
Correct |
13 ms |
14548 KB |
Output is correct |
5 |
Correct |
915 ms |
113856 KB |
Output is correct |
6 |
Correct |
865 ms |
99812 KB |
Output is correct |
7 |
Correct |
1234 ms |
132040 KB |
Output is correct |
8 |
Correct |
1635 ms |
153140 KB |
Output is correct |
9 |
Correct |
1692 ms |
153208 KB |
Output is correct |
10 |
Correct |
1693 ms |
153164 KB |
Output is correct |
11 |
Correct |
1311 ms |
152320 KB |
Output is correct |
12 |
Correct |
1246 ms |
152376 KB |
Output is correct |
13 |
Correct |
1236 ms |
152344 KB |
Output is correct |
14 |
Correct |
888 ms |
150476 KB |
Output is correct |
15 |
Correct |
870 ms |
149548 KB |
Output is correct |
16 |
Correct |
1070 ms |
150836 KB |
Output is correct |
17 |
Correct |
1018 ms |
150596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12244 KB |
Output is correct |
2 |
Correct |
8 ms |
12272 KB |
Output is correct |
3 |
Correct |
6 ms |
12244 KB |
Output is correct |
4 |
Correct |
6 ms |
12244 KB |
Output is correct |
5 |
Correct |
13 ms |
14112 KB |
Output is correct |
6 |
Correct |
13 ms |
14036 KB |
Output is correct |
7 |
Correct |
15 ms |
13572 KB |
Output is correct |
8 |
Correct |
13 ms |
14292 KB |
Output is correct |
9 |
Correct |
14 ms |
14276 KB |
Output is correct |
10 |
Correct |
13 ms |
14192 KB |
Output is correct |
11 |
Correct |
13 ms |
14164 KB |
Output is correct |
12 |
Correct |
13 ms |
14248 KB |
Output is correct |
13 |
Correct |
13 ms |
14540 KB |
Output is correct |
14 |
Correct |
13 ms |
14464 KB |
Output is correct |
15 |
Correct |
13 ms |
14292 KB |
Output is correct |
16 |
Correct |
15 ms |
14356 KB |
Output is correct |
17 |
Correct |
14 ms |
14292 KB |
Output is correct |
18 |
Correct |
16 ms |
14292 KB |
Output is correct |
19 |
Correct |
13 ms |
14204 KB |
Output is correct |
20 |
Correct |
13 ms |
14284 KB |
Output is correct |
21 |
Correct |
14 ms |
14292 KB |
Output is correct |
22 |
Correct |
17 ms |
14292 KB |
Output is correct |
23 |
Correct |
14 ms |
14288 KB |
Output is correct |
24 |
Correct |
15 ms |
14352 KB |
Output is correct |
25 |
Correct |
16 ms |
14292 KB |
Output is correct |
26 |
Correct |
14 ms |
14156 KB |
Output is correct |
27 |
Correct |
12 ms |
14164 KB |
Output is correct |
28 |
Correct |
12 ms |
14180 KB |
Output is correct |
29 |
Correct |
11 ms |
14156 KB |
Output is correct |
30 |
Correct |
13 ms |
14196 KB |
Output is correct |
31 |
Correct |
13 ms |
14292 KB |
Output is correct |
32 |
Correct |
13 ms |
14236 KB |
Output is correct |
33 |
Correct |
13 ms |
14544 KB |
Output is correct |
34 |
Correct |
17 ms |
14568 KB |
Output is correct |
35 |
Correct |
13 ms |
14548 KB |
Output is correct |
36 |
Correct |
6 ms |
12244 KB |
Output is correct |
37 |
Correct |
13 ms |
14292 KB |
Output is correct |
38 |
Correct |
17 ms |
14280 KB |
Output is correct |
39 |
Correct |
14 ms |
14236 KB |
Output is correct |
40 |
Correct |
975 ms |
123148 KB |
Output is correct |
41 |
Correct |
1410 ms |
110388 KB |
Output is correct |
42 |
Correct |
1226 ms |
95440 KB |
Output is correct |
43 |
Correct |
951 ms |
93932 KB |
Output is correct |
44 |
Correct |
878 ms |
97864 KB |
Output is correct |
45 |
Correct |
1628 ms |
134840 KB |
Output is correct |
46 |
Correct |
1580 ms |
134864 KB |
Output is correct |
47 |
Correct |
1593 ms |
134540 KB |
Output is correct |
48 |
Correct |
1550 ms |
134548 KB |
Output is correct |
49 |
Correct |
1679 ms |
134944 KB |
Output is correct |
50 |
Correct |
1737 ms |
149836 KB |
Output is correct |
51 |
Correct |
1608 ms |
150364 KB |
Output is correct |
52 |
Correct |
1642 ms |
149576 KB |
Output is correct |
53 |
Correct |
1862 ms |
135588 KB |
Output is correct |
54 |
Correct |
1790 ms |
135464 KB |
Output is correct |
55 |
Correct |
1851 ms |
135704 KB |
Output is correct |
56 |
Correct |
924 ms |
182720 KB |
Output is correct |
57 |
Correct |
918 ms |
166808 KB |
Output is correct |
58 |
Correct |
1075 ms |
151420 KB |
Output is correct |
59 |
Correct |
990 ms |
151080 KB |
Output is correct |
60 |
Correct |
1371 ms |
169208 KB |
Output is correct |
61 |
Correct |
1352 ms |
163396 KB |
Output is correct |
62 |
Correct |
1410 ms |
145692 KB |
Output is correct |
63 |
Correct |
744 ms |
135528 KB |
Output is correct |
64 |
Correct |
644 ms |
135448 KB |
Output is correct |
65 |
Correct |
894 ms |
136676 KB |
Output is correct |
66 |
Correct |
918 ms |
137032 KB |
Output is correct |
67 |
Correct |
6 ms |
12244 KB |
Output is correct |
68 |
Correct |
13 ms |
14548 KB |
Output is correct |
69 |
Correct |
14 ms |
14656 KB |
Output is correct |
70 |
Correct |
13 ms |
14548 KB |
Output is correct |
71 |
Correct |
915 ms |
113856 KB |
Output is correct |
72 |
Correct |
865 ms |
99812 KB |
Output is correct |
73 |
Correct |
1234 ms |
132040 KB |
Output is correct |
74 |
Correct |
1635 ms |
153140 KB |
Output is correct |
75 |
Correct |
1692 ms |
153208 KB |
Output is correct |
76 |
Correct |
1693 ms |
153164 KB |
Output is correct |
77 |
Correct |
1311 ms |
152320 KB |
Output is correct |
78 |
Correct |
1246 ms |
152376 KB |
Output is correct |
79 |
Correct |
1236 ms |
152344 KB |
Output is correct |
80 |
Correct |
888 ms |
150476 KB |
Output is correct |
81 |
Correct |
870 ms |
149548 KB |
Output is correct |
82 |
Correct |
1070 ms |
150836 KB |
Output is correct |
83 |
Correct |
1018 ms |
150596 KB |
Output is correct |
84 |
Correct |
909 ms |
126100 KB |
Output is correct |
85 |
Correct |
1270 ms |
113676 KB |
Output is correct |
86 |
Correct |
1060 ms |
84832 KB |
Output is correct |
87 |
Correct |
1781 ms |
139804 KB |
Output is correct |
88 |
Correct |
1770 ms |
139308 KB |
Output is correct |
89 |
Correct |
1658 ms |
139680 KB |
Output is correct |
90 |
Correct |
1793 ms |
139740 KB |
Output is correct |
91 |
Correct |
1736 ms |
139496 KB |
Output is correct |
92 |
Correct |
1917 ms |
151204 KB |
Output is correct |
93 |
Correct |
1830 ms |
154432 KB |
Output is correct |
94 |
Correct |
1974 ms |
140940 KB |
Output is correct |
95 |
Correct |
2037 ms |
141120 KB |
Output is correct |
96 |
Correct |
1973 ms |
141004 KB |
Output is correct |
97 |
Correct |
1961 ms |
141152 KB |
Output is correct |
98 |
Correct |
1444 ms |
140576 KB |
Output is correct |
99 |
Correct |
1455 ms |
140484 KB |
Output is correct |
100 |
Correct |
1475 ms |
140612 KB |
Output is correct |
101 |
Correct |
1477 ms |
140652 KB |
Output is correct |
102 |
Correct |
1436 ms |
143264 KB |
Output is correct |
103 |
Correct |
1387 ms |
143716 KB |
Output is correct |
104 |
Correct |
1412 ms |
143692 KB |
Output is correct |
105 |
Correct |
883 ms |
135588 KB |
Output is correct |
106 |
Correct |
705 ms |
135544 KB |
Output is correct |
107 |
Correct |
845 ms |
136520 KB |
Output is correct |
108 |
Correct |
874 ms |
136880 KB |
Output is correct |