oj.uz

Submission #7005

# Submission time Handle Problem Language Result Execution time Memory
7005 2014-07-12T09:23:33 Z ainta Factories (JOI14_factories) C++
100 / 100
 5512 ms 109776 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;
	Col[a] = 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 89764 KB Output is correct
2 Correct 980 ms 89764 KB Output is correct
3 Correct 1068 ms 89764 KB Output is correct
4 Correct 1020 ms 89764 KB Output is correct
5 Correct 1012 ms 89884 KB Output is correct
6 Correct 832 ms 89764 KB Output is correct
7 Correct 1036 ms 89764 KB Output is correct
8 Correct 992 ms 89764 KB Output is correct
9 Correct 964 ms 89888 KB Output is correct
10 Correct 836 ms 89764 KB Output is correct
11 Correct 1028 ms 89764 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 89764 KB Output is correct
2 Correct 2912 ms 89764 KB Output is correct
3 Correct 3412 ms 92368 KB Output is correct
4 Correct 2604 ms 89764 KB Output is correct
5 Correct 3144 ms 109776 KB Output is correct
6 Correct 3376 ms 92044 KB Output is correct
7 Correct 3180 ms 90144 KB Output is correct
8 Correct 2396 ms 89764 KB Output is correct
9 Correct 3508 ms 92076 KB Output is correct
10 Correct 3748 ms 90072 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2180 ms 89764 KB Output is correct
2 Correct 3532 ms 89764 KB Output is correct
3 Correct 2336 ms 91632 KB Output is correct
4 Correct 2912 ms 92064 KB Output is correct
5 Correct 5032 ms 91956 KB Output is correct
6 Correct 2648 ms 105440 KB Output is correct
7 Correct 2128 ms 89764 KB Output is correct
8 Correct 5272 ms 91684 KB Output is correct
9 Correct 5512 ms 91288 KB Output is correct
10 Correct 5492 ms 91708 KB Output is correct
11 Correct 1776 ms 94348 KB Output is correct
12 Correct 1452 ms 89764 KB Output is correct
13 Correct 1848 ms 89764 KB Output is correct
14 Correct 1920 ms 89764 KB Output is correct
15 Correct 2112 ms 90072 KB Output is correct
16 Correct 2580 ms 90064 KB Output is correct