Submission #6993

#	Time	Username	Problem	Language	Result	Execution time	Memory
6993		ainta	Factories (JOI14_factories)	C++98	15 / 100	6000 ms	189864 KiB

factories

#include "factories.h"
#include<algorithm>
#define INF 99999999999999999LL
using namespace std;
int L[1000010];
int nxt[1000010], pv[1000010], ed[1000010];
int n, Q[500010], pp[23][500010], sz, pcnt[500010];
int D[500010], par[500010];
long long D2[500010], dist[23][500010];
bool chk[500010];
void BFS(int a){
	int h = 0, t = 0, i, x;
	Q[++t] = a, D2[a] = 0, D[a] = 1;
	while (h < t){
		x = Q[++h];
		for (i = pv[x]; i; i = nxt[i]){
			if (!D[ed[i]] && !chk[ed[i]]){
				Q[++t] = ed[i];
				D2[ed[i]] = D2[x] + L[i];
				D[ed[i]] = 1;
				par[ed[i]] = x;
			}
		}
	}
	sz = t;
}
int Get_mid(int a){
	int i, x;
	BFS(a);
	for (i = sz; i >= 1; i--){
		x = Q[i];
		if (D[x] > sz / 2) break;
		D[par[x]] += D[x];
	}
	for (i = 1; i <= sz; i++){
		D[Q[i]] = 0;
	}
	return x;
}
void DFS(int a, int ppar, int pdis){
	int i, mid, x;
	mid = Get_mid(a);
	if (sz == 1){
		pp[pcnt[a]][a] = a;
		dist[pcnt[a]][a] = 0;
		pcnt[a]++;
		pp[pcnt[a]][a] = ppar;
		dist[pcnt[a]][a] = pdis;
		pcnt[a]++;
		return;
	}
	chk[mid] = true;
	for (i = pv[mid]; i; i = nxt[i]){
		x = ed[i];
		if (!chk[x]){
			DFS(x, mid, L[i]);
		}
	}
	pp[pcnt[mid]][mid] = mid;
	dist[pcnt[mid]][mid] = 0;
	pcnt[mid]++;
	chk[mid] = false;
	if (ppar == -1)return;
	BFS(a);
	for (i = 1; i <= sz; i++){
		x = Q[i];
		D[x] = 0;
		pp[pcnt[x]][x] = ppar;
		dist[pcnt[x]][x] = D2[x] + pdis;
		pcnt[x]++;
	}
}


long long Len[500010];

void Init(int N, int A[], int B[], int D[]) {
	int i, cnt = 0;
	for (i = 0; i < N - 1; i++){
		nxt[++cnt] = pv[A[i]]; ed[cnt] = B[i]; pv[A[i]] = cnt; L[cnt] = D[i];
		nxt[++cnt] = pv[B[i]]; ed[cnt] = A[i]; pv[B[i]] = cnt; L[cnt] = D[i];
	}
	DFS(0, -1, 0);
	for (i = 0; i < N; i++)Len[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
	register int i, j, x;
	long long Res = INF, t;
	for (i = 0; i != S; i++){
		x = X[i];
		for (j = 0; j != pcnt[x]; j++){
			if (Len[pp[j][x]] > dist[j][x]) Len[pp[j][x]] = dist[j][x];
		}
	}
	for (i = 0; i != T; i++){
		x = Y[i];
		for (j = 0; j != pcnt[x]; j++){
			t = Len[pp[j][x]] + dist[j][x];
			if (Res > t) Res = t;
		}
	}
	for (i = 0; i != S; i++){
		x = X[i];
		for (j = 0; j != pcnt[x]; j++){
			Len[pp[j][x]] = INF;
		}
	}
	return Res;
}

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