Submission #1304814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304814		icaijy	Factories (JOI14_factories)	C++20	0 / 100	8086 ms	289392 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;

}
void Init(signed N, signed A[], signed B[], signed D[]) {
	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=2e9;
	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;
}

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