Submission #379682

#	Time	Username	Problem	Language	Result	Execution time	Memory
379682		mode149256	Factories (JOI14_factories)	C++17	100 / 100	7999 ms	276060 KiB

factories

/*input

*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "factories.h"
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = 1e14;
const int MX = 500101;
const int L = 19;

int n;
vector<vector<pair<int, ll>>> edges;
vi dep;
vl toRoot;
vii p;
vll w;
vi in;
vi out;
int piv;

void dfs(int x, int par) {
	in[x] = piv++;
	for (auto u : edges[x]) {
		if (u.x == par) continue;

		int b = u.x;
		dep[b] = dep[x] + 1;
		toRoot[b] = toRoot[x] + u.y;
		p[b][0] = x;
		w[b][0] = u.y;
		for (int i = 1; i < L; ++i)
		{
			p[b][i] = p[p[b][i - 1]][i - 1];
			w[b][i] = w[b][i - 1] + w[p[b][i - 1]][i - 1];
		}
		dfs(u.x, x);
	}
	out[x] = piv;
}

// a is ancestor of b
int anc(int a, int b) {
	return in[a] < in[b] and out[b] <= out[a];
}

int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);

	// a
	// b
	for (int i = L - 1; i >= 0; --i)
	{
		if (dep[b] - (1 << i) >= dep[a])
			b = p[b][i];
	}
	if (a == b) return a;

	for (int i = L - 1; i >= 0; i--)
	{
		if (p[a][i] != p[b][i]) {
			a = p[a][i];
			b = p[b][i];
		}
	}
	return p[a][0];
}

ll dis(int a, int b) {
	int l = lca(a, b);
	return toRoot[a] + toRoot[b] - 2 * toRoot[l];
}

void make_lca() {
	dep = vi(n);
	p = vii(n, vi(L, 0));
	w = vll(n, vl(L, 0));
	toRoot = vl(n);
	in = vi(n);
	out = vi(n);

	dep[0] = 0;
	p[0][0] = 0;
	w[0][0] = 0;
	toRoot[0] = 0;
	piv = 0;

	dfs(0, -1);
}
vi kas;
vll low;

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	edges.resize(N);
	kas = vi(N, -1);
	for (int i = 0; i < N - 1; ++i)
	{
		int a = A[i];
		int b = B[i];
		int d = D[i];
		edges[a].emplace_back(b, d);
		edges[b].emplace_back(a, d);
	}

	make_lca();
	low = vll(n, vl{INF, INF});
}

ll Query(int S, int X[], int T, int Y[]) {
	vi visi;
	for (int i = 0; i < S; ++i) {
		visi.emplace_back(X[i]);
		kas[X[i]] = 1;
	}
	for (int i = 0; i < T; ++i) {
		visi.emplace_back(Y[i]);
		kas[Y[i]] = 2;
	}

	sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
		return in[a] < in[b];
	});

	for (int i = 1; i < S + T; ++i)
	{
		if (anc(visi[i - 1], visi[i]) or anc(visi[i], visi[i - 1])) continue;

		int l = lca(visi[i - 1], visi[i]);
		if (kas[l] == -1) {
			visi.emplace_back(l);
			kas[l] = 0;
		}
	}

	sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
		return in[a] < in[b];
	});

	// visi.erase(unique(visi.begin(), visi.end()), visi.end());

	// print(visi);
	ll ats = INF;

	stack<int> ver;

	ver.push(visi[0]);
	if (kas[visi[0]]) low[visi[0]][kas[visi[0]] - 1] = 0;

	for (int i = 1; i < (int)visi.size(); ++i)
	{
		while (!anc(ver.top(), visi[i])) {
			int a = ver.top(); ver.pop();
			int b = ver.top();

			ll d = dis(a, b);
			if (kas[a] + kas[b] == 3)
				ats = min(ats, d);

			//   b
			//  /  c
			// a

			low[b][0] = min(low[b][0], low[a][0] + d);
			low[b][1] = min(low[b][1], low[a][1] + d);
		}
		ver.push(visi[i]);
		if (kas[visi[i]]) low[visi[i]][kas[visi[i]] - 1] = 0;
	}

	while (ver.size() >= 2) {
		int a = ver.top(); ver.pop();
		int b = ver.top();
		ll d = dis(a, b);
		// printf("a = %d, b = %d, d = %lld\n", a, b, d);
		if (kas[a] + kas[b] == 3)
			ats = min(ats, d);

		//   b
		//  /  c
		// a

		low[b][0] = min(low[b][0], low[a][0] + d);
		low[b][1] = min(low[b][1], low[a][1] + d);
	}

	for (auto u : visi) {
		// printf("u = %d, low = %lld %lld\n", u, low[u][0], low[u][1]);
		ats = min(ats, low[u][0] + low[u][1]);
		kas[u] = -1;
		low[u][0] = low[u][1] = INF;
	}
	return ats;
}

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