Submission #285246

#	Time	Username	Problem	Language	Result	Execution time	Memory
285246		YJU	Factories (JOI14_factories)	C++14	0 / 100	8085 ms	16640 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=5e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
 
ll depth[N],parent[N],cut[N],sz[N],ms[N],dis[N];
pll anc[N][21];
vector<pll> v[N];
vector<ll> lis;
ll dist[N][25],lv[N];
 
ll distance(ll nda,ll ndb){
	ll tmp=0;
	if(depth[nda]<depth[ndb])swap(nda,ndb);
	for(int i=19;i>=0;i--){
		if(depth[anc[nda][i].X]>=depth[ndb]){
			tmp+=anc[nda][i].Y;
			nda=anc[nda][i].X;
		}
	}
	if(nda==ndb)return tmp;
	for(int i=19;i>=0;i--){
		if(anc[nda][i].X!=anc[ndb][i].X){
			tmp+=anc[nda][i].Y+anc[ndb][i].Y;
			nda=anc[nda][i].X;ndb=anc[ndb][i].X;
		}
	}
	return tmp+anc[nda][0].Y+anc[ndb][0].Y;
}
 
void PDFS(ll nd,ll pa,ll cost){
	depth[nd]=depth[pa]+1;
	anc[nd][0]=mp(pa,cost);
	REP1(i,20)anc[nd][i]=mp(anc[anc[nd][i-1].X][i-1].X,anc[nd][i-1].Y+anc[anc[nd][i-1].X][i-1].Y);
	for(auto i:v[nd]){
		if(i.X==pa)continue;
		PDFS(i.X,nd,i.Y);
	}
}

void buildd(ll nd,ll pa,ll L){
	for(auto i:v[nd]){
		if(i.X==pa||cut[i.X])continue;
		dist[i.X][L]=i.Y+dist[nd][L];
		buildd(i.X,nd,L);
	}
}
 
void DFS(ll id,ll par){
	sz[id]=1;ms[id]=0;
	for(auto i:v[id]){
		if(i.X==par||cut[i.X])continue;
		DFS(i.X,id);
		sz[id]+=sz[i.X];
	}
	for(auto i:v[id]){
		if(i.X==par||cut[i.X])continue;
		ms[id]=max(ms[id],sz[i.X]);
	}
	lis.pb(id);
}
 
void buildc(ll nd,ll pa){
	lis.clear();
	DFS(nd,0);
	ll cho=lis[0];
	for(auto i:lis)if(max(ms[cho],sz[nd]-sz[cho])>max(ms[i],sz[nd]-ms[i]))cho=i;
	parent[cho]=pa;
	cut[cho]=1;
	lv[cho]=lv[pa]+1;
	
	buildd(cho,0,lv[cho]);
	
	for(auto i:v[cho]){
		if(cut[i.X]||i.X==pa)continue;
		buildc(i.X,cho);
	}
}
 
void Init(int n,int A[],int B[],int D[]){
	REP1(i,n)dis[i]=INF;
	REP(i,n){
		++A[i];++B[i];
		v[B[i]].pb(mp(A[i],D[i]));
		v[A[i]].pb(mp(B[i],D[i]));
	}
	depth[0]=-1;
	PDFS(1,0,0);
	memset(lv,-1,sizeof(lv));
	lv[0]=0;
	buildc(1,0);
}
 
ll Query(int S,int x[],int T,int y[]){
	ll ans=INF;
	REP(i,S)++x[i];
	REP(i,T)++y[i];
	REP(i,S){
		ll nd=x[i];
		while(nd){
			while(dist[x[i]][lv[nd]]!=distance(x[i],nd));
			dis[nd]=min(dis[nd],dist[x[i]][lv[nd]]);
			nd=parent[nd];
		}
	}
	REP(i,T){
		ll nd=y[i];
		while(nd){
			while(dist[y[i]][lv[nd]]!=distance(y[i],nd));
			ans=min(ans,dis[nd]+dist[y[i]][lv[nd]]);
			nd=parent[nd];
		}
	}
	REP(i,S){
		ll nd=x[i];
		while(nd){
			dis[nd]=INF;
			nd=parent[nd];
		}
	}
	return ans;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67