Submission #6990

#	Time	Username	Problem	Language	Result	Execution time	Memory
6990		kriii	Factories (JOI14_factories)	C++14	100 / 100	2776 ms	127060 KiB

factories

#include "factories.h"
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int cnt,st[500005],ed[500005],par[500005][20],dep[500005]; long long len[500005]; bool chk[500005];
vector<pair<int, int> > grp[500005];

int lca(int x, int y)
{
	if (dep[x] > dep[y]) swap(x,y);

	int up = dep[y] - dep[x];
	for (int i=19;i>=0;i--) if (up & (1 << i)) y = par[y][i];

	if (x == y) return x;
	for (int i=19;i>=0;i--){
		if (par[x][i] != par[y][i]){
			x = par[x][i];
			y = par[y][i];
		}
	}
	return par[x][0];
}

void dfs(int x)
{
	chk[x] = 1;

	for (auto &p : grp[x]) if (!chk[p.first]){
		st[p.first] = ++cnt;
		dep[cnt] = dep[st[x]] + 1;
		len[cnt] = len[st[x]] + p.second;
		par[cnt][0] = st[x];
		for (int i=1;i<20;i++) par[cnt][i] = par[par[cnt][i-1]][i-1];
		dfs(p.first);
	}
	ed[st[x]] = cnt;
}

void Init(int N, int A[], int B[], int D[])
{
	for (int i=0;i<N-1;i++){
		grp[A[i]].push_back(make_pair(B[i],D[i]));
		grp[B[i]].push_back(make_pair(A[i],D[i]));
	}
	st[0] = ++cnt;
	dfs(0);
}

int cand[1000000],ext[500005],pcnt; long long U[500005],V[500005],ans;

int pdfs(int x)
{
	U[x] = V[x] = 1e16;
	if (ext[cand[x]] == 1) U[x] = 0;
	if (ext[cand[x]] == 2) V[x] = 0;

	int e = x + 1;
	while (e < pcnt && cand[e] <= ed[cand[x]]){
		int ne = pdfs(e);
		U[x] = min(U[x],U[e]+len[cand[e]]-len[cand[x]]);
		V[x] = min(V[x],V[e]+len[cand[e]]-len[cand[x]]);
		e = ne;
	}

	ans = min(ans,U[x]+V[x]);
	ext[cand[x]] = 0;
	
	return e;
}

long long Query(int S, int X[], int T, int Y[])
{
	pcnt = 0;
	for (int i=0;i<S;i++) cand[pcnt++] = st[X[i]], ext[st[X[i]]] = 1;
	for (int i=0;i<T;i++) cand[pcnt++] = st[Y[i]], ext[st[Y[i]]] = 2;
	sort(cand,cand+pcnt);
	for (int i=1;i<S+T;i++) cand[pcnt++] = lca(cand[i-1],cand[i]);
	sort(cand,cand+pcnt);
	pcnt = unique(cand,cand+pcnt) - cand;
	
	ans = 1e16;
	pdfs(0);

	return ans;
}

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