Submission #111528

#	Time	Username	Problem	Language	Result	Execution time	Memory
111528		autumn_eel	Factories (JOI14_factories)	C++14	100 / 100	7877 ms	243632 KiB

factories

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;

#include "factories.h"

vector<P>E[600000];
vector<ll>d[600000];

bool used[600000];
int sz[600000];

int par[600000];

ll dist[600000];

int szdfs(int v,int p){
	sz[v]=1;
	for(auto u:E[v]){
		if(u.second==p||used[u.second])continue;
		sz[v]+=szdfs(u.second,v);
	}
	return sz[v];
}

int search_centroid(int v,int p,int s){
	int ret=-1;
	int m=0;
	for(auto u:E[v]){
		if(u.second==p||used[u.second])continue;
		int res=search_centroid(u.second,v,s);
		if(res!=-1)ret=res;
		m=max(m,sz[u.second]);
	}
	if(max(m,s-sz[v])<=s/2){
		ret=v;
	}
	return ret;
}

void dfs(int v,int p,ll w){
	d[v].push_back(w);
	for(auto u:E[v]){
		if(u.second==p||used[u.second])continue;
		dfs(u.second,v,w+u.first);
	}
}

void build(int v,int p){
	szdfs(v,-1);
	int s=search_centroid(v,-1,sz[v]);
	used[s]=true;
	par[s]=p;
	dfs(s,-1,0);
	for(auto u:E[s]){
		if(used[u.second])continue;
		par[u.second]=s;
		build(u.second,s);
	}
}

void Init(int N, int A[], int B[], int D[]) {
	rep(i,N-1){
		E[A[i]].push_back(P(D[i],B[i]));
		E[B[i]].push_back(P(D[i],A[i]));
	}
	build(0,-1);
	memset(dist,0x3f,sizeof(dist));
}

long long Query(int S, int X[], int T, int Y[]) {
	rep(i,S){
		int v=X[i];
		for(int j=d[X[i]].size()-1;j>=0;j--){
			dist[v]=min(dist[v],d[X[i]][j]);
			if(j)v=par[v];
		}
	}
	ll ans=INF;
	rep(i,T){
		int v=Y[i];
		for(int j=d[Y[i]].size()-1;j>=0;j--){
			ans=min(ans,dist[v]+d[Y[i]][j]);
			if(j)v=par[v];
		}
	}
	rep(i,S){
		int v=X[i];
		for(int j=d[X[i]].size()-1;j>=0;j--){
			dist[v]=INF;
			if(j)v=par[v];
		}
	}
	return ans;
}

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