Submission #1165721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165721		_rain_	공장들 (JOI14_factories)	C++20	33 / 100	8090 ms	134392 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long LL;

const int N=(int)1e6;
const int MAXLOG=19;
const LL INF=1e18+7;
vector<pair<int,int>>ke[N+2];
#define fi first
#define se second

void add_canh(int u,int v,int c){
	ke[u].push_back({v,c}),ke[v].push_back({u,c});
	return;
}

int par[N+2][MAXLOG+2];
int h[N+2];
LL d[N+2];
void pre_dfs(int u,int p){
	h[u]=h[p]+1;
	par[u][0]=p;
	for(int i=1;i<=MAXLOG;++i) 
		par[u][i]=par[par[u][i-1]][i-1];
	for(auto&v:ke[u]){
		if (v.fi==p) continue;
		d[v.fi]=d[u]+v.se;
		pre_dfs(v.fi,u);
	}
	return;
}
int LCA(int u,int v){
	if (h[u]<h[v]) swap(u,v);
	for(int i=MAXLOG;i>=0;--i){
		if (h[par[u][i]]>=h[v])
			u=par[u][i];
	}
	if (u==v) return u;
	for(int i=MAXLOG;i>=0;--i){
		if (par[u][i]!=par[v][i]){
			u=par[u][i],v=par[v][i];
		}
	}
	return par[u][0];
}
LL getdist(int u,int v){
	int lca=LCA(u,v);
	return d[u]+d[v]-d[lca]*2;
}


class Centroid{
	private:
		vector<int>par,sub;
		vector<LL>mx;
		vector<bool>del;
	public:
		
		void init_size(int _n){
			par.resize(_n+2,0);
			sub.resize(_n+2,0);
			del.resize(_n+2,0);
			mx.resize(_n+2,INF);
		}
		
		void dfs(int u,int p){
			sub[u]=1;
			for(auto&v:ke[u]){
				if (v.fi==p || del[v.fi]) continue;
				dfs(v.fi,u);
				sub[u]+=sub[v.fi];
			}
		}
		
		int Find_centroid(int u,int p,int half){
			for(auto&v:ke[u]){
				if (del[v.fi] || v.fi==p) continue;
				if (sub[v.fi]>half) return Find_centroid(v.fi,u,half);
			}
			return u;
		}
		
		void build_centroid(int u,int p){
			dfs(u,u);
			u=Find_centroid(u,u,sub[u]/2);
			del[u]=true;
			par[u]=p;
			for(auto&v:ke[u]) if (del[v.fi]==0) build_centroid(v.fi,u);
		}
		
		void add(int u){
			int cur=u;
			while (cur!=0){
				mx[cur]=min(mx[cur],getdist(u,cur));
				cur=par[cur];
			}
		}
		void era(int u){
			int cur=u;
			while (cur!=0){
				mx[cur]=INF;
				cur=par[cur];
			}
		}
		LL Find(int u){
			int cur=u;
			LL ans=INF;
			while (cur!=0){
				ans=min(ans,getdist(cur,u)+mx[cur]);
				cur=par[cur];
			}
			return ans;
		}
};
Centroid tree;

void Init(int n,int a[],int b[],int d[]){
	for(int i=0;i<n-1;++i){
		++a[i],++b[i];
		add_canh(a[i],b[i],d[i]);
	}
	pre_dfs(1,0);
	tree.init_size(n);
	tree.build_centroid(1,0);

	return;
}
long long Query(int s,int x[],int t,int y[]){
	LL ans=INF;
	for(int i=0;i<s;++i) ++x[i];
	for(int i=0;i<t;++i) ++y[i];
	for(int i=0;i<s;++i) tree.add(x[i]);
	for(int i=0;i<t;++i) ans=min(ans,tree.Find(y[i]));
	for(int i=0;i<s;++i) tree.era(x[i]);
	return ans;
}

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