Submission #109308

#	Time	Username	Problem	Language	Result	Execution time	Memory
109308		Diuven	Factories (JOI14_factories)	C++14	100 / 100	5228 ms	143736 KiB

factories

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

typedef long long lint;
typedef pair<int, lint> pil;
typedef vector<int> Vint;
typedef vector<pil> Vpil;

const lint LNF = 2e18;
const int MAX = 5e5 + 10;
const int LG = 19;

int nu[MAX], ri[MAX], iv[MAX], dep[MAX], n;
int st[MAX][LG];
lint D[MAX];
vector<pil> G[MAX];

void dfs1(int v, int p, int cnt=0, lint sum=0){
	static int now = 0;
	nu[v] = ++now, ri[v] = nu[v], iv[nu[v]] = v;
	dep[v] = cnt, D[v] = sum;
	for(pil e:G[v]){
		int x; lint c; tie(x,c) = e;
		if(x==p) continue;
		st[x][0] = v;
		for(int i=1; i<LG; i++)
			st[x][i] = st[st[x][i-1]][i-1];
		dfs1(x,v,cnt+1,sum+c);
		ri[v] = ri[x];
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i=0; i<n-1; i++){
		int u = A[i], v = B[i], c = D[i];
		G[u].push_back({v,c});
		G[v].push_back({u,c});
	}
	dfs1(0,-1);
//	for(int i=0; i<n; i++) cout<<nu[i]<<' '<<ri[i]<<'\n';
}

int lca(int u, int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=LG-1; i>=0; i--)
		if(dep[u]-(1<<i)>=dep[v]) u = st[u][i];
	if(u==v) return u;
	for(int i=LG-1; i>=0; i--)
		if(st[u][i]!=st[v][i])
			u = st[u][i], v = st[v][i];
	return st[u][0];
}

int C[MAX];
lint A[MAX], B[MAX];
Vint V;

int idx;
lint dfs2(){
	int v = V[idx++];
	lint &a = A[v], &b = B[v], res = LNF;
	a = (C[v]==1 ? 0 : LNF);
	b = (C[v]==2 ? 0 : LNF);


	while(idx<int(V.size()) && V[idx]<=ri[iv[v]]){
		int x = V[idx];
		res = min(res, dfs2());
		a = min(a, D[iv[x]]-D[iv[v]] + A[x]);
		b = min(b, D[iv[x]]-D[iv[v]] + B[x]);
	}

	C[v] = 0, res = min(res, a+b);
	return res;
}


lint Query(int S, int X[], int T, int Y[]) {
	Vint P, Q; V.clear();
	for(int i=0; i<S; i++) P.push_back(nu[X[i]]);
	for(int i=0; i<T; i++) Q.push_back(nu[Y[i]]);

	for(int x:P) V.push_back(x), C[x] = 1;
	for(int x:Q) V.push_back(x), C[x] = 2;

	sort(V.begin(), V.end());

	for(int i=1, sz = int(V.size()); i<sz; i++)
		V.push_back(nu[lca(iv[V[i-1]], iv[V[i]])]);

	sort(V.begin(), V.end());
	V.resize(unique(V.begin(), V.end()) - V.begin());

	idx = 0;
	return dfs2();
}

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