oj.uz

답안 #6990

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6990 2014-07-12T07:36:38 Z kriii 공장들 (JOI14_factories) C++14
100 / 100
 2776 ms 127060 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 (auto &p : grp[x]) if (!chk[p.first]){
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 98188 KB Output is correct
2 Correct 960 ms 98320 KB Output is correct
3 Correct 952 ms 98320 KB Output is correct
4 Correct 932 ms 98320 KB Output is correct
5 Correct 848 ms 98336 KB Output is correct
6 Correct 868 ms 98320 KB Output is correct
7 Correct 916 ms 98320 KB Output is correct
8 Correct 972 ms 98320 KB Output is correct
9 Correct 860 ms 98332 KB Output is correct
10 Correct 860 ms 98320 KB Output is correct
11 Correct 904 ms 98320 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 98188 KB Output is correct
2 Correct 1492 ms 116800 KB Output is correct
3 Correct 1864 ms 117964 KB Output is correct
4 Correct 1108 ms 117864 KB Output is correct
5 Correct 1780 ms 127060 KB Output is correct
6 Correct 1984 ms 117756 KB Output is correct
7 Correct 1532 ms 101964 KB Output is correct
8 Correct 1008 ms 102252 KB Output is correct
9 Correct 1260 ms 102724 KB Output is correct
10 Correct 1516 ms 101916 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2096 ms 116800 KB Output is correct
2 Correct 2236 ms 116800 KB Output is correct
3 Correct 2016 ms 117476 KB Output is correct
4 Correct 2252 ms 117764 KB Output is correct
5 Correct 2624 ms 117692 KB Output is correct
6 Correct 2308 ms 124172 KB Output is correct
7 Correct 1864 ms 117864 KB Output is correct
8 Correct 2776 ms 117508 KB Output is correct
9 Correct 2772 ms 117244 KB Output is correct
10 Correct 2748 ms 117528 KB Output is correct
11 Correct 1276 ms 102968 KB Output is correct
12 Correct 1064 ms 102252 KB Output is correct
13 Correct 1448 ms 101884 KB Output is correct
14 Correct 1444 ms 101884 KB Output is correct
15 Correct 1448 ms 101916 KB Output is correct
16 Correct 1516 ms 101912 KB Output is correct