제출 #733800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
733800		PoPularPlusPlus	공장들 (JOI14_factories)	C++17	15 / 100	8077 ms	192908 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
 
using namespace std; 
 
#define ll long long
#define pb(e) push_back(e)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
 
const int N = 500002,L=20;
int n;
vector<pair<int,int>> adj[N];
int tin[N],tout[N],timer,up[N][L];
ll dis[N][L];
int p[N];
bool vis[N];
int siz[N];
ll res[N];

void dfs(int node , int par , int di){
	tin[node] = timer++;
	up[node][0] = par;
	dis[node][0] = di;
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
		dis[node][i] = dis[node][i-1] + dis[up[node][i-1]][i-1];
	}
	for(auto i : adj[node]){
		if(i.vf != par){
			dfs(i.vf , node , i.vs);
		}
	}
	tout[node] = timer++;
}
 
bool is_lca(int x , int y){
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}
 
int find(int x , int y){
	if(is_lca(x,y))return x;
	if(is_lca(y,x))return y;
	for(int i = L - 1; i >= 0; i--){
		if(!is_lca(up[x][i] , y))x = up[x][i];
	}
	return up[x][0];
}

void size_init(int node , int par){
	siz[node] = 1;
	for(auto i : adj[node]){
		if(i.vf != par && !vis[i.vf]){
			size_init(i.vf,node);
			siz[node] += siz[i.vf];
		}
	}
}

int find_centroid(int node , int par , int total){
	for(auto i :  adj[node]){
		if(!vis[i.vf] && i.vf != par && siz[i.vf] >= total/2)return find_centroid(i.vf , node , total);
	}
	return node;
}

void centroid_decomposition(int node ,int par){
	size_init(node , node);
	node = find_centroid(node , node , siz[node]);
	p[node] = par;
	vis[node] = 1;
	for(auto i : adj[node]){
		if(!vis[i.vf]){
			centroid_decomposition(i.vf , node);
		}
	}
}
 
void Init(int nn, int A[], int B[], int D[]) {
	n = nn;
	for(int i = 0; i < n-1; i++){
		adj[A[i]].pb(mp(B[i],D[i]));
		adj[B[i]].pb(mp(A[i],D[i]));
	}
	timer = 0;
	dfs(0,0,0);
	memset(vis,0,sizeof vis);
	centroid_decomposition(0,-1);
	memset(res,-1,sizeof res);
}
 
ll cal(int x , int y){
	if(x == y)return 0;
	if(is_lca(x,y))swap(x,y);
	ll ans = 0;
	for(int i = L - 1; i >= 0; i--){
		if(!is_lca(up[x][i] , y)){
			ans += dis[x][i];
			x = up[x][i];
		}
	}
	ans += dis[x][0];
	return ans;
}

long long Query(int a, int X[], int b, int Y[]) {
	ll ans = 1e18;
	for(int i = 0; i < a; i++){
		int node = X[i];
		res[node] = 0;
		node = p[node];
		while(node != -1){
			int lca = find(X[i] , node);
			ll distance = cal(X[i],lca) + cal(node,lca);
			if(res[node] == -1 || res[node] > distance){
				res[node] = distance;
				//cout << node << ' ' << X[i] << ' ' << lca << ' ' << distance << '\n';
			}
			node = p[node];
		}
	}
		for(int i = 0; i < b; i++){
			int node = Y[i];
			while(node != -1){
				if(res[node] != -1){
					int lca = find(Y[i],node);
					ll distance = cal(Y[i],lca) + cal(node,lca);
					ans = min(ans , res[node] + distance);
					//cout << node << ' ' << res[node] << ' ' << distance << '\n';
				}
				node = p[node];
			}
		}
		for(int i = 0; i < a; i++){
			int node = X[i];
			while(node != -1){
				if(res[node]==-1)break;
				res[node] = -1;
				node = p[node];
			}
		}
		return ans;
}

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