oj.uz

Submission #6996

# Submission time Handle Problem Language Result Execution time Memory
6996 2014-07-12T08:15:25 Z ainta Factories (JOI14_factories) C++
15 / 100
 6000 ms 189864 KB 
#include "factories.h"
#include<algorithm>
#define INF 99999999999999999LL
using namespace std;
int L[1000010];
int nxt[1000010], pv[500010], ed[1000010];
int n, Q[500010], pp[23][500010], sz, pcnt[500010];
int D[500010], par[500010], D3[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, M=999999999, y;
	BFS(a);
	if (sz == 1){
		D[a] = 0;
		return -1;
	}
	for (i = sz; i >= 1; i--){
		x = Q[i];
		if (D3[x] < sz - D[x])D3[x] = sz - D[x];
		if (M>D3[x])M = D3[x], y = x;
		if (i == 1)break;
		D[par[x]] += D[x];
		if (D3[par[x]] < D[x])D3[par[x]] = D[x];
	}
	for (i = 1; i <= sz; i++){
		D[Q[i]] = 0;
		D3[Q[i]] = 0;
	}
	return y;
}
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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 189864 KB Output is correct
2 Correct 372 ms 189864 KB Output is correct
3 Correct 460 ms 189864 KB Output is correct
4 Correct 412 ms 189864 KB Output is correct
5 Correct 456 ms 189864 KB Output is correct
6 Correct 276 ms 189864 KB Output is correct
7 Correct 408 ms 189864 KB Output is correct
8 Correct 416 ms 189864 KB Output is correct
9 Correct 436 ms 189864 KB Output is correct
10 Correct 256 ms 189864 KB Output is correct
11 Correct 420 ms 189864 KB Output is correct

Subtask #2
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 189864 KB Output is correct
2 Correct 5704 ms 189864 KB Output is correct
3 Execution timed out 6000 ms 189860 KB Program timed out
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6000 ms 189860 KB Program timed out
2 Halted 0 ms 0 KB -