제출 #111824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
111824		autumn_eel	공장들 (JOI14_factories)	C++14	33 / 100	8080 ms	223536 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 s){
	bool flag=true;
	int p=-1;
	while(flag){
		flag=false;
		for(auto u:E[v]){
			if(u.second==p||used[u.second])continue;
			if(sz[u.second]>s/2){
				flag=true;
				p=v;
				v=u.second;
				break;
			}
		}
	}
	return v;
}

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,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: 0 / 67