oj.uz

Submission #7007

# Submission time Handle Problem Language Result Execution time Memory
7007 2014-07-12T09:27:09 Z ainta Factories (JOI14_factories) C++
100 / 100
 5376 ms 117588 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 97576 KB Output is correct
2 Correct 1040 ms 97576 KB Output is correct
3 Correct 1056 ms 97576 KB Output is correct
4 Correct 1012 ms 97576 KB Output is correct
5 Correct 1000 ms 97664 KB Output is correct
6 Correct 812 ms 97576 KB Output is correct
7 Correct 1040 ms 97576 KB Output is correct
8 Correct 1056 ms 97576 KB Output is correct
9 Correct 1020 ms 97660 KB Output is correct
10 Correct 856 ms 97576 KB Output is correct
11 Correct 1124 ms 97576 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 97576 KB Output is correct
2 Correct 2928 ms 97576 KB Output is correct
3 Correct 3332 ms 100180 KB Output is correct
4 Correct 2636 ms 97576 KB Output is correct
5 Correct 3376 ms 117588 KB Output is correct
6 Correct 3524 ms 99860 KB Output is correct
7 Correct 3668 ms 97956 KB Output is correct
8 Correct 3408 ms 97576 KB Output is correct
9 Correct 3472 ms 99888 KB Output is correct
10 Correct 3920 ms 97884 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2116 ms 97576 KB Output is correct
2 Correct 3696 ms 97576 KB Output is correct
3 Correct 2440 ms 99444 KB Output is correct
4 Correct 3012 ms 99876 KB Output is correct
5 Correct 4920 ms 99772 KB Output is correct
6 Correct 2812 ms 113256 KB Output is correct
7 Correct 2256 ms 97576 KB Output is correct
8 Correct 5376 ms 99496 KB Output is correct
9 Correct 5216 ms 99100 KB Output is correct
10 Correct 5296 ms 99524 KB Output is correct
11 Correct 1580 ms 100248 KB Output is correct
12 Correct 1356 ms 97576 KB Output is correct
13 Correct 1668 ms 97576 KB Output is correct
14 Correct 1704 ms 97576 KB Output is correct
15 Correct 1928 ms 97888 KB Output is correct
16 Correct 2020 ms 97876 KB Output is correct