제출 #374968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374968		peijar	공장들 (JOI14_factories)	C++17	0 / 100	74 ms	67948 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXP = 20;
vector<vector<pair<int, int>>> g;
int nbSommets;
vector<int> tempsDeb, tempsFin;
vector<int> par[MAXP], parWeight[MAXP];
vector<int> depthWeight, depth;
int temps;
const int nbFeuilles = 1 << 20;
const int INF = 1e18;

struct Segtree
{
	int seg[2 * nbFeuilles];

	Segtree()
	{
		for (int i(0); i < 2 * nbFeuilles; ++i)
			seg[i] = INF;
	}

	void update(int pos, int val)
	{
		pos += nbFeuilles;
		seg[pos] = val;
		while (pos > 1)
		{
			pos /= 2;
			seg[pos] = min(seg[2*pos], seg[2*pos+1]);
		}
	}

	int query(int deb, int fin)
	{
		deb += nbFeuilles, fin += nbFeuilles;
		int ret = INF;

		/*
		 * 1
		 * 2 3
		 * 4 5 6 7
		 */
		while (deb < fin)
		{
			if (deb % 2)
				ret = min(ret, seg[deb]);
			deb = (deb + 1)/2;
			if (fin % 2 == 0)
				ret = min(ret, seg[fin]);
			fin = (fin - 1) / 2;
		}
		if (deb == fin)
			ret = min(ret, seg[deb]);
		return ret;
	}
};

Segtree seg1, seg2;


void dfs(int u)
{
	tempsDeb[u] = temps++;
	for (auto [v,w] : g[u])
		if (v != par[0][u])
		{
			par[0][v] = u;
			parWeight[0][v] = w;
			depth[v] = depth[u] + 1;
			depthWeight[v] = depthWeight[u] + w;
			dfs(v);
		}
	tempsFin[u] = temps++;
}

void initLca()
{
	for (int p(1); p < MAXP; ++p)
		for (int u(0); u < nbSommets; ++u)
		{
			par[p][u] = par[p-1][par[p-1][u]];
			parWeight[p][u] = parWeight[p-1][par[p-1][u]] + parWeight[p-1][u];
		}
}

int calcLca(int u, int v)
{
	if (depth[u] < depth[v]) swap(u, v);
	int diff = depth[u] - depth[v];
	for (int p(0); p < MAXP; ++p)
		if ((1<<p) & diff)
			u = par[p][u];
	for (int p(MAXP-1); p >= 0; --p)
		if (par[p][u] != par[p][v])
		{
			u = par[p][u];
			v = par[p][v];
		}
	if (u != v)
		return par[0][u];
	return u;
}

int calcDis(int u, int v)
{
	return depthWeight[u] + depthWeight[v] - 2 * depthWeight[calcLca(u, v)];
}

void Init(signed N, signed A[], signed B[], signed D[]) 
{
	nbSommets = N;
	g.resize(nbSommets);
	tempsDeb.resize(nbSommets);
	tempsFin.resize(nbSommets);
	depth.resize(nbSommets);
	depthWeight.resize(nbSommets);
	for (int p(0); p < MAXP; ++p)
		par[p].resize(nbSommets), parWeight[p].resize(nbSommets);
	for (int i(0); i < N-1; ++i)
	{
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	temps = 0;
	dfs(0);
	initLca();
}

int Query(signed S, signed X[], signed T, signed Y[]) {
	vector<int> sommetsRequete;
	for (int i(0); i < S; ++i)
		sommetsRequete.push_back(X[i]);
	for (int i(0); i < T; ++i)
		sommetsRequete.push_back(Y[i]);
	sort(sommetsRequete.begin(), sommetsRequete.end(),
			[&](int u, int v)
			{
				return make_pair(tempsDeb[u], u) < make_pair(tempsDeb[v], v);
			});
	sort(sommetsRequete.begin(), sommetsRequete.end());
	vector<int> potentielsLca;
	for (int i(0); i < S; ++i)
		potentielsLca.push_back(X[i]);
	for (int i(0); i < T; ++i)
		potentielsLca.push_back(Y[i]);
	for (int i(1); i < (int)sommetsRequete.size(); ++i)
		potentielsLca.push_back(calcLca(sommetsRequete[i-1], sommetsRequete[i]));
	int ret = INF;
	for (int i(0); i < S; ++i)
		seg1.update(tempsDeb[X[i]], depthWeight[X[i]]);
	for (int i(0); i < T; ++i)
		seg2.update(tempsDeb[Y[i]], depthWeight[Y[i]]);
	for (auto lca : potentielsLca)
	{
		ret = min(ret, seg1.query(tempsDeb[lca], tempsFin[lca])
				+ seg2.query(tempsDeb[lca], tempsFin[lca])
				- 2 * depthWeight[lca]);
	}
	for (int i(0); i < S; ++i)
		for (int j(0); j < T; ++j)
			assert(calcDis(X[i], Y[j]) >= ret);

	for (int i(0); i < T; ++i)
		seg2.update(tempsDeb[Y[i]], INF);
	for (int i(0); i < S; ++i)
		seg1.update(tempsDeb[X[i]], INF);
	return ret;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67