#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;
stack<int> st;
LL f[MAXN*4],lazy[MAXN*4],val[MAXN];
int dfs(int x,int y,LL path) {
val[x]=path;
sub[x]=1;
par[x]=y;
for(int i=0;i<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&&v[x].size()>1)
swap(v[x][0].st,v[x][1].st);
for(int i=0;i<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<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 build(int x,int l,int r) {
f[x]=lazy[x]=1e17;
if(l==r) return;
int md=(l+r)/2;
build(x*2,l,md);
build(x*2+1,md+1,r);
}
void push(int x,int l,int r) {
f[x]=min(f[x],lazy[x]-2*val[who[r]]);
lazy[x*2]=min(lazy[x*2],lazy[x]);
lazy[x*2+1]=min(lazy[x*2+1],lazy[x]);
lazy[x]=1e17;
}
void upd(int x,int l,int r,int ll,int rr,LL v) {
if(lazy[x]!=1e17)
push(x,l,r);
if(!vis[x]) {
vis[x]=1;
st.push(x);
}
if(l>rr||r<ll)
return;
if(l>=ll&&r<=rr) {
lazy[x]=v;
push(x,l,r);
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)
push(x,l,r);
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);
build(1,0,n-1);
}
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;
while(!st.empty()) {
t=st.top();
st.pop();
vis[t]=0;
f[t]=lazy[t]=1e17;
if(t*2<MAXN*4)
lazy[t*2]=1e17;
if(t*2+1<MAXN*4)
lazy[t*2+1]=1e17;
}
return ret;
}
Compilation message
factories.cpp: In function 'int dfs(int, int, long long int)':
factories.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();++i) {
^
factories.cpp: In function 'void hld(int, int)':
factories.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();++i)
^
factories.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();++i) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
90700 KB |
Output is correct |
| 2 |
Correct |
2479 ms |
90964 KB |
Output is correct |
| 3 |
Correct |
2459 ms |
90964 KB |
Output is correct |
| 4 |
Correct |
2366 ms |
90964 KB |
Output is correct |
| 5 |
Correct |
1463 ms |
91184 KB |
Output is correct |
| 6 |
Correct |
1386 ms |
91000 KB |
Output is correct |
| 7 |
Correct |
2316 ms |
90964 KB |
Output is correct |
| 8 |
Correct |
2176 ms |
90964 KB |
Output is correct |
| 9 |
Correct |
1429 ms |
91188 KB |
Output is correct |
| 10 |
Correct |
1306 ms |
91000 KB |
Output is correct |
| 11 |
Correct |
2503 ms |
90964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
90700 KB |
Output is correct |
| 2 |
Execution timed out |
6000 ms |
109444 KB |
Execution timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6000 ms |
111864 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
