#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 = 1e7+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 = 2e5+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 |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
2 ms |
5076 KB |
Output is correct |
5 |
Correct |
7 ms |
6996 KB |
Output is correct |
6 |
Correct |
9 ms |
6996 KB |
Output is correct |
7 |
Correct |
8 ms |
6612 KB |
Output is correct |
8 |
Correct |
10 ms |
7304 KB |
Output is correct |
9 |
Correct |
10 ms |
7252 KB |
Output is correct |
10 |
Correct |
10 ms |
7220 KB |
Output is correct |
11 |
Correct |
12 ms |
7232 KB |
Output is correct |
12 |
Correct |
10 ms |
7252 KB |
Output is correct |
13 |
Correct |
10 ms |
7476 KB |
Output is correct |
14 |
Correct |
10 ms |
7508 KB |
Output is correct |
15 |
Correct |
12 ms |
7340 KB |
Output is correct |
16 |
Correct |
11 ms |
7344 KB |
Output is correct |
17 |
Correct |
12 ms |
7344 KB |
Output is correct |
18 |
Correct |
10 ms |
7344 KB |
Output is correct |
19 |
Correct |
11 ms |
7220 KB |
Output is correct |
20 |
Correct |
9 ms |
7252 KB |
Output is correct |
21 |
Correct |
9 ms |
7252 KB |
Output is correct |
22 |
Correct |
9 ms |
7252 KB |
Output is correct |
23 |
Correct |
12 ms |
7220 KB |
Output is correct |
24 |
Correct |
12 ms |
7224 KB |
Output is correct |
25 |
Correct |
9 ms |
7352 KB |
Output is correct |
26 |
Correct |
8 ms |
7096 KB |
Output is correct |
27 |
Correct |
8 ms |
7124 KB |
Output is correct |
28 |
Correct |
8 ms |
7224 KB |
Output is correct |
29 |
Correct |
8 ms |
7092 KB |
Output is correct |
30 |
Correct |
12 ms |
7264 KB |
Output is correct |
31 |
Correct |
10 ms |
7284 KB |
Output is correct |
32 |
Correct |
10 ms |
7252 KB |
Output is correct |
33 |
Correct |
10 ms |
7472 KB |
Output is correct |
34 |
Correct |
10 ms |
7552 KB |
Output is correct |
35 |
Correct |
12 ms |
7552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5076 KB |
Output is correct |
2 |
Correct |
10 ms |
7276 KB |
Output is correct |
3 |
Correct |
10 ms |
7264 KB |
Output is correct |
4 |
Correct |
10 ms |
7304 KB |
Output is correct |
5 |
Correct |
1006 ms |
120404 KB |
Output is correct |
6 |
Correct |
1412 ms |
108076 KB |
Output is correct |
7 |
Correct |
1242 ms |
93100 KB |
Output is correct |
8 |
Correct |
877 ms |
90916 KB |
Output is correct |
9 |
Correct |
874 ms |
94736 KB |
Output is correct |
10 |
Correct |
1725 ms |
132684 KB |
Output is correct |
11 |
Correct |
1818 ms |
132752 KB |
Output is correct |
12 |
Correct |
1690 ms |
132500 KB |
Output is correct |
13 |
Correct |
1653 ms |
132480 KB |
Output is correct |
14 |
Correct |
1607 ms |
132976 KB |
Output is correct |
15 |
Correct |
1652 ms |
148428 KB |
Output is correct |
16 |
Correct |
1601 ms |
148960 KB |
Output is correct |
17 |
Correct |
1611 ms |
148144 KB |
Output is correct |
18 |
Correct |
1852 ms |
133868 KB |
Output is correct |
19 |
Correct |
1918 ms |
133736 KB |
Output is correct |
20 |
Correct |
1862 ms |
134052 KB |
Output is correct |
21 |
Runtime error |
959 ms |
344156 KB |
Execution killed with signal 11 |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5160 KB |
Output is correct |
2 |
Correct |
9 ms |
7508 KB |
Output is correct |
3 |
Correct |
10 ms |
7552 KB |
Output is correct |
4 |
Correct |
11 ms |
7508 KB |
Output is correct |
5 |
Correct |
880 ms |
107776 KB |
Output is correct |
6 |
Correct |
815 ms |
93544 KB |
Output is correct |
7 |
Correct |
1136 ms |
126512 KB |
Output is correct |
8 |
Correct |
1672 ms |
148388 KB |
Output is correct |
9 |
Correct |
1687 ms |
148368 KB |
Output is correct |
10 |
Correct |
1635 ms |
148340 KB |
Output is correct |
11 |
Correct |
1228 ms |
147528 KB |
Output is correct |
12 |
Correct |
1238 ms |
147580 KB |
Output is correct |
13 |
Correct |
1266 ms |
147688 KB |
Output is correct |
14 |
Correct |
877 ms |
145572 KB |
Output is correct |
15 |
Correct |
817 ms |
144516 KB |
Output is correct |
16 |
Correct |
997 ms |
146088 KB |
Output is correct |
17 |
Correct |
978 ms |
145860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
2 ms |
5076 KB |
Output is correct |
5 |
Correct |
7 ms |
6996 KB |
Output is correct |
6 |
Correct |
9 ms |
6996 KB |
Output is correct |
7 |
Correct |
8 ms |
6612 KB |
Output is correct |
8 |
Correct |
10 ms |
7304 KB |
Output is correct |
9 |
Correct |
10 ms |
7252 KB |
Output is correct |
10 |
Correct |
10 ms |
7220 KB |
Output is correct |
11 |
Correct |
12 ms |
7232 KB |
Output is correct |
12 |
Correct |
10 ms |
7252 KB |
Output is correct |
13 |
Correct |
10 ms |
7476 KB |
Output is correct |
14 |
Correct |
10 ms |
7508 KB |
Output is correct |
15 |
Correct |
12 ms |
7340 KB |
Output is correct |
16 |
Correct |
11 ms |
7344 KB |
Output is correct |
17 |
Correct |
12 ms |
7344 KB |
Output is correct |
18 |
Correct |
10 ms |
7344 KB |
Output is correct |
19 |
Correct |
11 ms |
7220 KB |
Output is correct |
20 |
Correct |
9 ms |
7252 KB |
Output is correct |
21 |
Correct |
9 ms |
7252 KB |
Output is correct |
22 |
Correct |
9 ms |
7252 KB |
Output is correct |
23 |
Correct |
12 ms |
7220 KB |
Output is correct |
24 |
Correct |
12 ms |
7224 KB |
Output is correct |
25 |
Correct |
9 ms |
7352 KB |
Output is correct |
26 |
Correct |
8 ms |
7096 KB |
Output is correct |
27 |
Correct |
8 ms |
7124 KB |
Output is correct |
28 |
Correct |
8 ms |
7224 KB |
Output is correct |
29 |
Correct |
8 ms |
7092 KB |
Output is correct |
30 |
Correct |
12 ms |
7264 KB |
Output is correct |
31 |
Correct |
10 ms |
7284 KB |
Output is correct |
32 |
Correct |
10 ms |
7252 KB |
Output is correct |
33 |
Correct |
10 ms |
7472 KB |
Output is correct |
34 |
Correct |
10 ms |
7552 KB |
Output is correct |
35 |
Correct |
12 ms |
7552 KB |
Output is correct |
36 |
Correct |
2 ms |
5076 KB |
Output is correct |
37 |
Correct |
10 ms |
7276 KB |
Output is correct |
38 |
Correct |
10 ms |
7264 KB |
Output is correct |
39 |
Correct |
10 ms |
7304 KB |
Output is correct |
40 |
Correct |
1006 ms |
120404 KB |
Output is correct |
41 |
Correct |
1412 ms |
108076 KB |
Output is correct |
42 |
Correct |
1242 ms |
93100 KB |
Output is correct |
43 |
Correct |
877 ms |
90916 KB |
Output is correct |
44 |
Correct |
874 ms |
94736 KB |
Output is correct |
45 |
Correct |
1725 ms |
132684 KB |
Output is correct |
46 |
Correct |
1818 ms |
132752 KB |
Output is correct |
47 |
Correct |
1690 ms |
132500 KB |
Output is correct |
48 |
Correct |
1653 ms |
132480 KB |
Output is correct |
49 |
Correct |
1607 ms |
132976 KB |
Output is correct |
50 |
Correct |
1652 ms |
148428 KB |
Output is correct |
51 |
Correct |
1601 ms |
148960 KB |
Output is correct |
52 |
Correct |
1611 ms |
148144 KB |
Output is correct |
53 |
Correct |
1852 ms |
133868 KB |
Output is correct |
54 |
Correct |
1918 ms |
133736 KB |
Output is correct |
55 |
Correct |
1862 ms |
134052 KB |
Output is correct |
56 |
Runtime error |
959 ms |
344156 KB |
Execution killed with signal 11 |
57 |
Halted |
0 ms |
0 KB |
- |