제출 #1086269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086269		4QT0R	공장들 (JOI14_factories)	C++17	18 / 100	8067 ms	180412 KiB

factories

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

ll oo=1e18;
vector<pair<int,ll>> graph[500003];
ll dep[500003];
ll real_dep[500003];
ll jmp[500003][20];

int lca(int a, int b){
	if (dep[a]<dep[b])swap(a,b);
	for (int i = 19; i>=0; i--){
		if (dep[jmp[a][i]]>=dep[b])a=jmp[a][i];
	}
	if (a==b)return a;
	for (int i = 19; i>=0; i--){
		if (jmp[a][i]!=jmp[b][i]){
			a=jmp[a][i];
			b=jmp[b][i];
		}
	}
	return jmp[a][0];
}

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

void prep(int v, int p){
	jmp[v][0]=p;
	for (int i = 1; i<20; i++)jmp[v][i]=jmp[jmp[v][i-1]][i-1];
	for (auto [u,d] : graph[v]){
		if (u==p)continue;
		dep[u]=dep[v]+1;
		real_dep[u]=real_dep[v]+d;
		prep(u,v);
	}
}

int n;

void Init(int N, int A[], int B[], int D[]){
	n=N;
	for (int i = 0; i<N-1; i++){
		graph[A[i]].push_back({B[i],D[i]});
		graph[B[i]].push_back({A[i],D[i]});
	}
	prep(0,0);
}

ll odl[500003];
bool fin[500003];

ll Query(int S, int X[], int T, int Y[]){
	if (S<=1300 && T<=1300){
		ll ans=oo;
		for (int i = 0; i<S; i++){
			for (int j = 0; j<T; j++){
				ans=min(ans,dist(X[i],Y[j]));
			}
		}
		return ans;
	}
	for (int i = 0; i<T; i++)fin[Y[i]]=true;
	fill(odl,odl+n,oo);
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
	for (int i = 0; i<S; i++){
		odl[X[i]]=0;
		pq.push({0,X[i]});
	}
	while(pq.size()){
		auto [v,d] = pq.top();
		pq.pop();
		if (d>odl[v])continue;
		if (fin[v]){
			for (int i = 0; i<T; i++)fin[Y[i]]=false;
			return d;
		}
		for (auto [u,x] : graph[v]){
			if (d+x<odl[u]){
				odl[u]=d+x;
				pq.push({odl[u],u});
			}
		}
	}
	return -1;
}

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