#include "factories.h"
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int MAXN=500005;
vector<pii> v[MAXN];
int head[MAXN],par[MAXN],in[MAXN],out[MAXN],tme,sub[MAXN],who[MAXN],vis[MAXN*4],n,sum;
stack<int> st;
LL f[MAXN*8],lazy[MAXN*8],val[MAXN];
int dfs(int x,int y,LL path) {
val[x]=path;
sub[x]=1;
par[x]=y;
for(int i=0;i<(int)v[x].size();++i) {
if(v[x][i].st!=y)
sub[x]+=dfs(v[x][i].st,x,path+v[x][i].nd);
}
return sub[x];
}
void hld(int x,int y) {
in[x]=++tme;
who[tme]=x;
if(v[x][0].st==y&&(int)v[x].size()>1)
swap(v[x][0].st,v[x][1].st);
for(int i=0;i<(int)v[x].size();++i)
if(v[x][i].st!=y&&sub[v[x][i].st]>sub[v[x][0].st])
swap(v[x][0],v[x][i]);
for(int i=0;i<(int)v[x].size();++i) {
if(v[x][i].st==y)
continue;
if(i==0)
head[v[x][i].st]=head[x];
else head[v[x][i].st]=v[x][i].st;
hld(v[x][i].st,x);
}
out[x]=tme;
}
void upd(int x,int l,int r,int ll,int rr,LL v) {
if(lazy[x]!=1e17) {
f[x]=min(f[x],lazy[x]-2*val[who[r]]);
if(l!=r) {
lazy[x*2]=min(lazy[x*2],lazy[x]);
lazy[x*2+1]=min(lazy[x*2+1],lazy[x]);
}
lazy[x]=1e17;
}
if(!vis[x]) {
vis[x]=1;
st.push(x);
}
if(l>rr||r<ll)
return;
if(l>=ll&&r<=rr) {
lazy[x]=v;
f[x]=min(f[x],lazy[x]-2*val[who[r]]);
if(l!=r) {
lazy[x*2]=min(lazy[x*2],lazy[x]);
lazy[x*2+1]=min(lazy[x*2+1],lazy[x]);
}
lazy[x]=1e17;
return;
}
int md=(l+r)/2;
upd(x*2,l,md,ll,rr,v);
upd(x*2+1,md+1,r,ll,rr,v);
f[x]=min(f[x*2],f[x*2+1]);
}
LL que(int x,int l,int r,int ll,int rr) {
if(lazy[x]!=1e17) {
f[x]=min(f[x],lazy[x]-2*val[who[r]]);
if(l!=r) {
lazy[x*2]=min(lazy[x*2],lazy[x]);
lazy[x*2+1]=min(lazy[x*2+1],lazy[x]);
}
lazy[x]=1e17;
}
if(!vis[x]) {
vis[x]=1;
st.push(x);
}
if(l>rr||r<ll)
return 1e17;
if(l>=ll&&r<=rr)
return f[x];
int md=(l+r)/2;
return min(que(x*2,l,md,ll,rr),que(x*2+1,md+1,r,ll,rr));
}
LL find(int x) {
LL ret=1e17;
while(x!=-1) {
ret=min(ret,que(1,0,n-1,in[head[x]],in[x]));
x=par[head[x]];
}
return ret;
}
void update(int x,LL v) {
while(x!=-1) {
upd(1,0,n-1,in[head[x]],in[x],v);
x=par[head[x]];
}
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<n-1;++i) {
v[A[i]].pb(mp(B[i],D[i]));
v[B[i]].pb(mp(A[i],D[i]));
}
dfs(0,-1,0);
head[0]=0;
hld(0,0);
for(int i=0;i<MAXN*4;++i)
f[i]=lazy[i]=1e17;
}
long long Query(int s, int x[], int tt, int y[]) {
LL ret=1e17;
for(int i=0;i<tt;++i)
update(y[i],val[y[i]]);
for(int i=0;i<s;++i)
ret=min(ret,find(x[i])+val[x[i]]);
int t;
sum+=st.size();
while(!st.empty()) {
t=st.top();
st.pop();
vis[t]=0;
f[t]=lazy[t]=lazy[t*2]=lazy[t*2+1]=1e17;
}
assert(sum<600000000);
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
121948 KB |
Output is correct |
| 2 |
Correct |
2356 ms |
122212 KB |
Output is correct |
| 3 |
Correct |
2166 ms |
122212 KB |
Output is correct |
| 4 |
Correct |
2253 ms |
122212 KB |
Output is correct |
| 5 |
Correct |
1296 ms |
122436 KB |
Output is correct |
| 6 |
Correct |
1546 ms |
122248 KB |
Output is correct |
| 7 |
Correct |
2456 ms |
122212 KB |
Output is correct |
| 8 |
Correct |
2079 ms |
122212 KB |
Output is correct |
| 9 |
Correct |
1293 ms |
122436 KB |
Output is correct |
| 10 |
Correct |
1363 ms |
122248 KB |
Output is correct |
| 11 |
Correct |
2373 ms |
122212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
121948 KB |
Output is correct |
| 2 |
Execution timed out |
6000 ms |
140692 KB |
Execution timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6000 ms |
143112 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
