Submission #1304847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304847		icaijy	공장들 (JOI14_factories)	C++20	33 / 100	8095 ms	322288 KiB

factories

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

pair<int,int> par[500005][30];
vector<pair<int,int>> adj[500005];
int depth[500005];
void dfs(int cur,int d){
	depth[cur]=d;
	for (auto [j,i]:adj[cur]){
		if (par[cur][0].second==i) continue;
		par[i][0]={j,cur};
		dfs(i,d+1);
	}
}
int dis(int x,int y){
	int ret=0;
	if (depth[x]<depth[y]) swap(x,y);
	for (int k=19;k>=0;k--){
		if (depth[par[x][k].second]>=depth[y]){
			ret+=par[x][k].first;
			x=par[x][k].second;
		}
	}
	if (x==y) return ret;
	for (int k=19;k>=0;k--){
		if (par[x][k].second!=par[y][k].second){
			ret+=par[x][k].first;
			x=par[x][k].second;
			ret+=par[y][k].first;
			y=par[y][k].second;
		}
	}
	return ret+par[x][0].first+par[y][0].first;

}
int n;
void Init(signed N, signed A[], signed B[], signed D[]) {
	n=N;
	for (int i=0;i<N-1;i++){
		adj[A[i]+1].push_back({D[i],B[i]+1});
		adj[B[i]+1].push_back({D[i],A[i]+1});
	}
	dfs(1,1);
	for (int k=1;k<20;k++) for (int i=1;i<=N;i++) par[i][k]={par[i][k-1].first+par[par[i][k-1].second][k-1].first,par[par[i][k-1].second][k-1].second};
}

int Query(signed S, signed X[], signed T, signed Y[]){
	int ret=1e18;
	if (S*T<8000){
		for (int i=0;i<S;i++){
			for (int j=0;j<T;j++){
				ret=min(ret,dis(X[i]+1,Y[j]+1));
			}
		}
		return ret;
	}
	else{
		if (S>T){
			swap(S,T);
			swap(X,Y);
		}
		unordered_set<int> st;
		for (int i=0;i<T;i++) st.insert(Y[i]+1);
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
		vector<int> ans(n+1,1e18);
		for (int i=0;i<S;i++){
			pq.push({0,X[i]+1});
			ans[X[i]+1]=0;
		}
		while (true){
			auto pqt=pq.top();
			pq.pop();
			if (ans[pqt.second]<pqt.first) continue;
			if (st.count(pqt.second)) return pqt.first;
			for (auto [j,i]:adj[pqt.second]){
				if (ans[i]<=j+pqt.first) continue;
				ans[i]=j+pqt.first;
				pq.push({ans[i],i});
			}
		}
	}
}

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