Submission #656613

#	Time	Username	Problem	Language	Result	Execution time	Memory
656613		TranGiaHuy1508	Factories (JOI14_factories)	C++17	100 / 100	2521 ms	447936 KiB

factories

#include <bits/stdc++.h>
using namespace std;

#include "factories.h"

using ll = long long;

namespace {
	template <class T>
	struct RMQ{
		vector<vector<T>> table;
		ll _n, _lg;

		RMQ() = default;
		RMQ(vector<T> &v){
			_n = v.size(); _lg = log2(_n);
			table.assign(_lg + 1, vector<T>(_n));

			for (ll i = 0; i < _n; i++) table[0][i] = v[i];

			for (ll j = 1; j <= _lg; j++){
				for (ll i = 0; i + (1 << j) <= _n; i++){
					table[j][i] = min(table[j-1][i], table[j-1][i + (1 << (j-1))]);
				}
			}
		}

		T get(int l, int r){
			ll j = log2(r - l + 1);
			return min(table[j][l], table[j][r - (1 << j) + 1]);
		}
	};

	ll n;
	const ll inf = 1e18;
	vector<vector<pair<ll, ll>>> adj;
	vector<pair<ll, ll>> euler_tour;
	vector<ll> dist, d1, d2;
	vector<ll> tin, tout, firstocc, op;
	ll timer = 0;
	RMQ<pair<ll, ll>> rmq;

	void euler_dfs(ll x, ll p = -1, ll d = 0){
		firstocc[x] = euler_tour.size();
		euler_tour.emplace_back(d, x);
		tin[x] = timer++;
		for (auto [k, w]: adj[x]){
			if (k == p) continue;
			dist[k] = dist[x] + w;
			euler_dfs(k, x, d+1);
			euler_tour.emplace_back(d, x);
		}
		tout[x] = timer++;
	}

	ll LCA(ll x, ll y){
		if (firstocc[x] > firstocc[y]) swap(x, y);
		return rmq.get(firstocc[x], firstocc[y]).second;
	}

	ll distance(ll x, ll y){
		return dist[x] + dist[y] - dist[LCA(x, y)] * 2;
	}
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	adj.resize(n);
	euler_tour.clear();
	tin.resize(n);
	tout.resize(n);
	firstocc.resize(n);
	dist.assign(n, 0);
	d1.assign(n, inf);
	d2.assign(n, inf);
	op.assign(n, 0);

	for (ll i = 0; i < n-1; i++){
		adj[A[i]].emplace_back(B[i], D[i]);
		adj[B[i]].emplace_back(A[i], D[i]);
	}

	euler_dfs(0);
	rmq = RMQ<pair<ll, ll>>(euler_tour);
}

ll Query(int S, int X[], int T, int Y[]){
	for (ll i = 0; i < S; i++) op[X[i]] = 1;
	for (ll i = 0; i < T; i++) op[Y[i]] = 2;

	vector<ll> Z;
	for (ll i = 0; i < S; i++) Z.push_back(X[i]);
	for (ll i = 0; i < T; i++) Z.push_back(Y[i]);

	sort(Z.begin(), Z.end(), [&](ll a, ll b){
		return tin[a] < tin[b];
	});

	for (ll i = 1; i < S + T; i++){
		ll lca = LCA(Z[i-1], Z[i]);
		if (!op[lca]){
			op[lca] = 3;
			Z.push_back(lca);
		}
	}

	sort(Z.begin(), Z.end(), [&](ll a, ll b){
		return tin[a] < tin[b];
	});

	stack<ll> parent;
	ll res = inf;

	for (ll i = 0; i < (ll)Z.size(); i++){
		while (!parent.empty()){
			if (tin[parent.top()] <= tin[Z[i]] && tout[Z[i]] <= tout[parent.top()]) break;
			ll tp = parent.top(); parent.pop();
			res = min(res, d1[tp] + d2[tp]);
			if (!parent.empty()){
				ll dt = distance(parent.top(), tp);
				d1[parent.top()] = min(d1[parent.top()], d1[tp] + dt);
				d2[parent.top()] = min(d2[parent.top()], d2[tp] + dt);
			}
		}

		parent.push(Z[i]);
		if (op[Z[i]] == 1) d1[Z[i]] = 0;
		if (op[Z[i]] == 2) d2[Z[i]] = 0;
	}

	while (!parent.empty()){
		ll tp = parent.top(); parent.pop();
		res = min(res, d1[tp] + d2[tp]);
		if (!parent.empty()){
			ll dt = distance(parent.top(), tp);
			d1[parent.top()] = min(d1[parent.top()], d1[tp] + dt);
			d2[parent.top()] = min(d2[parent.top()], d2[tp] + dt);
		}
	}

	for (auto i: Z) op[i] = 0;
	for (auto i: Z) d1[i] = d2[i] = inf;

	return res;
}

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