oj.uz

Submission #6992

# Submission time Handle Problem Language Result Execution time Memory
6992 2014-07-12T07:38:31 Z kriii Factories (JOI14_factories) C++
100 / 100
 2876 ms 127064 KB 
#include "factories.h"
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int cnt,st[500005],ed[500005],par[500005][20],dep[500005]; long long len[500005]; bool chk[500005];
vector<pair<int, int> > grp[500005];

int lca(int x, int y)
{
	if (dep[x] > dep[y]) swap(x,y);

	int up = dep[y] - dep[x];
	for (int i=19;i>=0;i--) if (up & (1 << i)) y = par[y][i];

	if (x == y) return x;
	for (int i=19;i>=0;i--){
		if (par[x][i] != par[y][i]){
			x = par[x][i];
			y = par[y][i];
		}
	}
	return par[x][0];
}

void dfs(int x)
{
	chk[x] = 1;

	for (int i=0;i<grp[x].size();i++){
		pair<int, int> p = grp[x][i];
		if (chk[p.first]) continue;
		st[p.first] = ++cnt;
		dep[cnt] = dep[st[x]] + 1;
		len[cnt] = len[st[x]] + p.second;
		par[cnt][0] = st[x];
		for (int i=1;i<20;i++) par[cnt][i] = par[par[cnt][i-1]][i-1];
		dfs(p.first);
	}
	ed[st[x]] = cnt;
}

void Init(int N, int A[], int B[], int D[])
{
	for (int i=0;i<N-1;i++){
		grp[A[i]].push_back(make_pair(B[i],D[i]));
		grp[B[i]].push_back(make_pair(A[i],D[i]));
	}
	st[0] = ++cnt;
	dfs(0);
}

int cand[1000000],ext[500005],pcnt; long long U[500005],V[500005],ans;

int pdfs(int x)
{
	U[x] = V[x] = 1e16;
	if (ext[cand[x]] == 1) U[x] = 0;
	if (ext[cand[x]] == 2) V[x] = 0;

	int e = x + 1;
	while (e < pcnt && cand[e] <= ed[cand[x]]){
		int ne = pdfs(e);
		U[x] = min(U[x],U[e]+len[cand[e]]-len[cand[x]]);
		V[x] = min(V[x],V[e]+len[cand[e]]-len[cand[x]]);
		e = ne;
	}

	ans = min(ans,U[x]+V[x]);
	ext[cand[x]] = 0;
	
	return e;
}

long long Query(int S, int X[], int T, int Y[])
{
	pcnt = 0;
	for (int i=0;i<S;i++) cand[pcnt++] = st[X[i]], ext[st[X[i]]] = 1;
	for (int i=0;i<T;i++) cand[pcnt++] = st[Y[i]], ext[st[Y[i]]] = 2;
	sort(cand,cand+pcnt);
	for (int i=1;i<S+T;i++) cand[pcnt++] = lca(cand[i-1],cand[i]);
	sort(cand,cand+pcnt);
	pcnt = unique(cand,cand+pcnt) - cand;
	
	ans = 1e16;
	pdfs(0);

	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 98188 KB Output is correct
2 Correct 928 ms 98320 KB Output is correct
3 Correct 908 ms 98320 KB Output is correct
4 Correct 896 ms 98320 KB Output is correct
5 Correct 848 ms 98328 KB Output is correct
6 Correct 844 ms 98320 KB Output is correct
7 Correct 888 ms 98320 KB Output is correct
8 Correct 916 ms 98320 KB Output is correct
9 Correct 852 ms 98336 KB Output is correct
10 Correct 788 ms 98320 KB Output is correct
11 Correct 860 ms 98320 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 98188 KB Output is correct
2 Correct 1528 ms 116800 KB Output is correct
3 Correct 1856 ms 117968 KB Output is correct
4 Correct 1080 ms 117864 KB Output is correct
5 Correct 1844 ms 127064 KB Output is correct
6 Correct 1944 ms 117752 KB Output is correct
7 Correct 1556 ms 101964 KB Output is correct
8 Correct 920 ms 102252 KB Output is correct
9 Correct 1320 ms 102724 KB Output is correct
10 Correct 1448 ms 101912 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2092 ms 116800 KB Output is correct
2 Correct 2160 ms 116800 KB Output is correct
3 Correct 2008 ms 117476 KB Output is correct
4 Correct 2216 ms 117760 KB Output is correct
5 Correct 2640 ms 117692 KB Output is correct
6 Correct 2336 ms 124172 KB Output is correct
7 Correct 1672 ms 117864 KB Output is correct
8 Correct 2784 ms 117512 KB Output is correct
9 Correct 2876 ms 117244 KB Output is correct
10 Correct 2764 ms 117524 KB Output is correct
11 Correct 1232 ms 102968 KB Output is correct
12 Correct 1012 ms 102252 KB Output is correct
13 Correct 1408 ms 101884 KB Output is correct
14 Correct 1404 ms 101884 KB Output is correct
15 Correct 1428 ms 101916 KB Output is correct
16 Correct 1504 ms 101908 KB Output is correct