oj.uz

Submission #7004

# Submission time Handle Problem Language Result Execution time Memory
7004 2014-07-12T09:18:36 Z ainta Factories (JOI14_factories) C++
0 / 100
 2276 ms 89764 KB 
#include "factories.h"
#include<algorithm>
#define INF 999999999999999LL
#define pll pair<long long, long long>
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;

pll DFS2(int a){
	pll r = pll(INF, INF), t;
	if (Col[a] == 1)r.first = 0;
	if (Col[a] == 2)r.second = 0;
	int x;
	while (pv != cnt && w[pv] <= ran[a]){
		x = w[pv]; pv++;
		t = DFS2(x);
		r.first = min(r.first, t.first + D[x] - D[a]);
		r.second = min(r.second, t.second + D[x] - D[a]);
	}
	Res = min(Res, r.first + r.second);
	return r;
}

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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 89764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 89764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 2276 ms 89764 KB Output isn't correct
2 Halted 0 ms 0 KB -