Submission #7007

#	Time	Username	Problem	Language	Result	Execution time	Memory
7007		ainta	Factories (JOI14_factories)	C++98	100 / 100	5376 ms	117588 KiB

factories

#include "factories.h"
#include<algorithm>
#define INF 999999999999999LL
using namespace std;
int Nxt[1000100], ed[1000100], L[1000100], P[500010];
int par[19][500010], num[500010], cnt, ran[500010], Dep[500010];
long long D[500010];

void DFS(int a, int pp){
	num[a] = ++cnt;
	int i;
	for (i = P[a]; i; i = Nxt[i]){
		if (pp != ed[i]){
			par[0][cnt + 1] = num[a];
			Dep[cnt + 1] = Dep[num[a]] + 1;
			D[cnt + 1] = D[num[a]] + L[i];
			DFS(ed[i], a);
		}
	}
	ran[num[a]] = cnt;
}

int LCA(int a, int b){
	if (Dep[a] < Dep[b])swap(a, b);
	int d = Dep[a] - Dep[b], c = 0;
	while (d){
		if (d & 1){
			a = par[c][a];
		}
		c++;
		d >>= 1;
	}
	c = 19;
	while (c--){
		if (par[c][a] != par[c][b])a = par[c][a], b = par[c][b];
	}
	if (a != b)a = par[0][a];
	return a;
}

void Init(int N, int A[], int B[], int D[]) {
	int i, c = 0, j;
	for (i = 0; i < N - 1; i++){
		Nxt[++c] = P[A[i]]; ed[c] = B[i]; P[A[i]] = c; L[c] = D[i];
		Nxt[++c] = P[B[i]]; ed[c] = A[i]; P[B[i]] = c; L[c] = D[i];
	}
	DFS(0, -1);
	for (i = 0; i < 18; i++){
		for (j = 1; j <= N; j++){
			par[i + 1][j] = par[i][par[i][j]];
		}
	}
}

int w[1000010], pv, Col[500010];
long long Res, GS[500010], GT[500010];

void DFS2(int a){
	long long S = INF, T = INF;
	if (Col[a] == 1)S =0;
	if (Col[a] == 2)T = 0;
	Col[a] = 0;
	int x;
	while (pv != cnt && w[pv] <= ran[a]){
		x = w[pv]; pv++;
		DFS2(x);
		S = min(S, GS[x] + D[x] - D[a]);
		T = min(T, GT[x] + D[x] - D[a]);
	}
	Res = min(Res, S + T);
	GS[a] = S, GT[a] = T;
}

long long Query(int S, int X[], int T, int Y[]) {
	int i;
	cnt = 0;
	for (i = 0; i < S; i++)w[cnt++] = num[X[i]], Col[num[X[i]]] = 1;
	for (i = 0; i < T; i++)w[cnt++] = num[Y[i]], Col[num[Y[i]]] = 2;
	sort(w, w + cnt);
	for (i = cnt - 1; i; i--){
		w[cnt++] = LCA(w[i], w[i - 1]);
	}
	sort(w, w + cnt);
	cnt = unique(w, w + cnt) - w;
	Res = INF, pv = 0;
	DFS2(1);
	return Res;
}

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