Submission #6991

# Submission time Handle Problem Language Result Execution time Memory
6991 2014-07-12T07:38:00 Z kriii Factories (JOI14_factories) C++14
Compilation error
0 ms 0 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> = 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;
}

Compilation message

factories.cpp: In function 'void dfs(int)':
factories.cpp:31:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
factories.cpp:32:18: error: expected unqualified-id before '=' token
factories.cpp:33:11: error: 'p' was not declared in this scope
factories.cpp:34:6: error: 'p' was not declared in this scope