Submission #374987

#	Time	Username	Problem	Language	Result	Execution time	Memory
374987		peijar	Factories (JOI14_factories)	C++17	100 / 100	3496 ms	482600 KiB

factories

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

vector<vector<pair<int, int>>> g;
signed nbSommets;
vector<signed> tempsDeb, tempsFin;
vector<int> depthWeight, depth;
vector<signed> eulerTour;
vector<signed> posEuler;
signed temps;
const signed 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(signed deb, signed fin)
	{
		deb += nbFeuilles, fin += nbFeuilles;
		int ret = INF;

		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;

const signed MAXP = 21;

struct Sparse
{
	pair<signed, signed> sparse[MAXP][1 << MAXP];
	signed log2[1 << MAXP];

	void build()
	{
		log2[1] = 0;
		for (int i(2); i < (1 << MAXP); ++i)
			log2[i] = 1 + log2[i/2];
		for (int i(0); i < (int)eulerTour.size(); ++i)
			sparse[0][i] = make_pair(depth[eulerTour[i]], eulerTour[i]);
		for (int p(1); p < MAXP; ++p)
			for (int i(0); i < (int)eulerTour.size(); ++i)
				sparse[p][i] = min(sparse[p-1][i],
						sparse[p-1][min((int)eulerTour.size()-1, i + (1 << (p-1)))]);
	}

	signed getMin(signed deb, signed fin)
	{
		if (deb > fin) swap(deb, fin);
		signed lg = log2[fin-deb+1];
		return min(sparse[lg][deb], sparse[lg][fin - (1<<lg)+1]).second;
	}
};

Sparse sparse;


void dfs(signed u, int p=0)
{
	tempsDeb[u] = temps++;
	posEuler[u] = (signed)eulerTour.size();
	eulerTour.push_back(u);
	for (auto [v,w] : g[u])
		if (v != p)
		{
			depth[v] = depth[u] + 1;
			depthWeight[v] = depthWeight[u] + w;
			dfs(v, u);
			eulerTour.push_back(u);
		}
	tempsFin[u] = temps++;
}

signed calcLca(signed u, signed v)
{
	return sparse.getMin(posEuler[u], posEuler[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);
	posEuler.resize(nbSommets);
	for (signed 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);
	sparse.build();
}

vector<signed> potentielsLca;
vector<signed> sommetsRequete;

int Query(signed S, signed X[], signed T, signed Y[]) {
	for (signed i(0); i < S; ++i)
		sommetsRequete.push_back(X[i]);
	for (signed i(0); i < T; ++i)
		sommetsRequete.push_back(Y[i]);
	sort(sommetsRequete.begin(), sommetsRequete.end(),
			[&](signed u, signed v)
			{
				return tempsDeb[u]< tempsDeb[v];
			});
	potentielsLca.reserve((signed)sommetsRequete.size()  - 1);
	for (signed i(1); i < (signed)sommetsRequete.size(); ++i)
		potentielsLca.push_back(calcLca(sommetsRequete[i-1], sommetsRequete[i]));
	sommetsRequete.clear();
	int ret = INF;
	for (signed i(0); i < S; ++i)
		seg1.update(tempsDeb[X[i]], depthWeight[X[i]]);
	for (signed 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]);
	}
	potentielsLca.clear();

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

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