Submission #1270967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270967		WH8	Factories (JOI14_factories)	C++20	100 / 100	7552 ms	202580 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define f first 
#define s second
#define iii tuple<int,int,int>
#define int long long
using namespace std;

vector<vector<int>> up(500005, vector<int>(20, -1));
int dist[500005][2];
vector<vector<pair<int,int>>> al(500005);
vector<int> in(500005, -1);
int t=0;
int depth[500005], distroot[500005];
void dfs(int x, int p){
	in[x]=t++;
	for(auto [to, d]:al[x]){
		if(to==p)continue;
		depth[to]=depth[x]+1;
		distroot[to]=distroot[x]+d;
		up[to][0]=x;
		dfs(to, x);
	}
}

int kpar(int x, int k){
	for(int i=0;i<20;i++){
		if((1<<i)&k)x=up[x][i];
	}
	return x;
}

int ispar(int a, int b){
	if(depth[a]>depth[b])swap(a,b);
	if(kpar(b, depth[b]-depth[a])==a)return true;
	return false;
}

int lca(int a, int b){
	if(depth[a] < depth[b])swap(a,b);
	a=kpar(a, depth[a]-depth[b]);
	for(int i=19;i>=0;i--){
		if(up[a][i]==up[b][i])continue;
		a=up[a][i], b=up[b][i];
	}
	return up[a][0];
}

void Init(signed N, signed A[], signed B[], signed D[]) {
	for(int i=0;i<N;i++){
		al[A[i]].push_back({B[i],D[i]});
		al[B[i]].push_back({A[i],D[i]});
	}
	dfs(0, -1);
	for(int i=1;i<20;i++){
		for(int j=0;j<N;j++){
			if(up[j][i-1] != -1)up[j][i]=up[up[j][i-1]][i-1];
		}
	}
	//~ for(int i=0;i<N;i++){
		//~ cout<<depth[i]<<endl;
	//~ }
	//~ printf("lca of 3 5 is %lld\n", lca(3, 5));
}


long long Query(signed S, signed X[], signed T, signed Y[]) {
	vector<int> nodes;
	
	for(int i=0;i<S;i++)nodes.push_back(X[i]);
	for(int i=0;i<T;i++)nodes.push_back(Y[i]);
	sort(nodes.begin(),nodes.end(),[&](auto a, auto b){
		return in[a]<in[b];
	});
	for(int i=0;i<S+T-1;i++){
		int l=lca(nodes[i], nodes[i+1]);
		//~ printf("%lld %lld : %lld\n", nodes[i], nodes[i+1], l);
		nodes.push_back(l);
	}
	sort(nodes.begin(),nodes.end(),[&](auto a, auto b){
		return in[a]<in[b];
	});
	nodes.erase(unique(nodes.begin(),nodes.end()), nodes.end());
	for(auto it:nodes){
		al[it].clear();
		dist[it][0]=dist[it][1]=1e15;
		
	}
	priority_queue<iii,vector<iii>,greater<iii>> pq;
	for(int i=0;i<S;i++){
		dist[X[i]][0]=0;
		pq.push({0, X[i], 0});
	}
	for(int i=0;i<T;i++){
		dist[Y[i]][1]=0;
		if(dist[Y[i]][0]==0)return 0;
		pq.push({0, Y[i], 1});
	}
	vector<int> stk;
	stk.push_back(nodes[0]);
	for(int i=1;i<(int)nodes.size();i++){
		while(!ispar(stk.back(), nodes[i])){
			stk.pop_back();
		}
		int sd=abs(distroot[nodes[i]]-distroot[stk.back()]);
		al[nodes[i]].push_back({stk.back(), sd});
		al[stk.back()].push_back({nodes[i], sd});
		stk.push_back(nodes[i]);
	}
	//~ for(auto it : nodes){
		//~ printf("node %lld: ",it);
		//~ for(auto [to, d] : al[it]){
			//~ printf("(%lld, %lld) ",to,d);
		//~ }
		//~ cout<<endl;
	//~ }
	int ans=1e15;
	while(!pq.empty()){
		auto [cd, x, st] = pq.top();pq.pop();
		if(dist[x][st]<cd)continue;
		for(auto [to, d]:al[x]){
			int cand=cd+d;
			if(dist[to][st]<cand)continue;
			dist[to][st]=cand;
			pq.push({cand, to, st});
		}
	}
	for(auto it:nodes){
		ans=min(ans, dist[it][0]+dist[it][1]);
	}
	//~ for(auto it:nodes){
		//~ printf("%lld, dist0: %lld dist1: %lld\n", it, dist[it][0], dist[it][1]);
	//~ }
	return ans;
}

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