제출 #21062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
21062		sbansalcs	공장들 (JOI14_factories)	C++14	33 / 100	6000 ms	254096 KiB

factories

#include "factories.h"
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
const int N = 500005;
typedef long long ll;
int dp[N][20],depth[N],subtree[N],vis[N],parent[N];
ll dist[N],XX[N][20];int PP[N][20];
int A[N];ll B[N];
vector<pair<int,int>> adj[N];
int logt[N];

int QUERY=0;

void dfs1(int v, int p, int dep, ll x)	{
	dp[v][0]=p;
	depth[v]=dep;
	dist[v]=x;
	for(int i=1;i<=logt[dep];i++)	dp[v][i]=dp[dp[v][i-1]][i-1];
	int c;
	for(auto e:adj[v])	{
		c=e.first;
		if(c==p)	continue;
		dfs1(c,v,dep+1,x+e.second);
	}
}

int find_centroid(int v, int p, int x)	{
	int c;
	for(auto e:adj[v])	{
		c=e.first;
		if(c==p || vis[c] || subtree[c]<=x)	continue;
		return find_centroid(c,v,x);
	}
	return v;
}

void dfs2(int v, int p)	{
	int c;
	subtree[v]=1;
	for(auto e:adj[v])	{
		c=e.first;
		if(c==p || vis[c] )	continue;
		dfs2(c,v);
		subtree[v]+=subtree[c];
	}
}

inline int lca(int a, int b)	{
	if(depth[a]>depth[b])	swap(a,b);
	for(int i=logt[depth[b]];i>=0;i--)	{
		if(depth[b]-(1<<i)>=depth[a])	b=dp[b][i];
	}
	if(a==b)	return a;
	for(int i=logt[depth[b]];i>=0;i--)	{
		if(dp[a][i]!=dp[b][i])	a=dp[a][i],b=dp[b][i];
	}
	return dp[a][0];
}

inline ll distance(int a, int b)	{
	return dist[a]+dist[b]-2*dist[lca(a,b)];
}

void process(int v, int p)	{

	dfs2(v,0);
	int u=find_centroid(v,0,subtree[v]/2);
	vis[u]=1;
	parent[u]=p;
	int p2=u;
	int i=0;
	PP[u][i]=p2;
	while(p2!=-1)	{
		XX[u][i]=distance(p2,u);
		p2=parent[p2];i++;
		PP[u][i]=p2;
	}
	assert(i<=20);
	int c;
	for(auto e:adj[u])	{
		c=e.first;
		if(vis[c])	continue;
		process(c,u);
	}
}


void Init(int n, int A[], int B[], int D[]) {
	for(int i=0;i<=n-2;i++)	{
		adj[A[i]+1].push_back({B[i]+1,D[i]});
		adj[B[i]+1].push_back({A[i]+1,D[i]});
	}
	logt[0]=-1;
	for(int i=1;i<=n;i++)	{
		logt[i]=logt[i-1];
		if((i&-i)==i)	logt[i]++;
	}
	dfs1(1,0,0,0);
	process(1,-1);
}

long long Query(int S, int X[], int T, int Y[]) {
	QUERY++;
	int u,v;
	for(int i=0;i<S;i++)	{
		u=X[i]+1;
		for(int j=0;PP[u][j]!=-1;j++)	{
			v=PP[u][j];
			if(A[v]!=QUERY)	{
				A[v]=QUERY;B[v]=XX[u][j];
			}
			else if(B[v]>XX[u][j])	{
				B[v]=XX[u][j];
			}
		}
	}
	ll ans=1e17;
		for(int i=0;i<T;i++)	{
		u=Y[i]+1;
		for(int j=0;PP[u][j]!=-1;j++)	{
			v=PP[u][j];
			if(A[v]==QUERY)	{
				ans=min(XX[u][j]+B[v],ans);
			}

		}
	}

  	return ans;
}

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