Submission #779439

#	Time	Username	Problem	Language	Result	Execution time	Memory
779439		TranGiaHuy1508	Factories (JOI14_factories)	C++17	100 / 100	4582 ms	183544 KiB

factories

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

#include "factories.h"

#define distance _distance

using ll = long long;
using ii = pair<int, int>;

namespace {
	struct Edge{
		int to;
		ll d;
	};

	// Main variables
	const ll inf = 1e18;

	int n, lg, timer;
	vector<int> depth, tin, tout;
	vector<ll> distance;
	vector<vector<int>> parent;
	vector<vector<Edge>> adj;

	// Main functions
	void dfs(int x, int p = -1, int d = 0, ll dist = 0){
		depth[x] = d;
		distance[x] = dist;
		tin[x] = timer++;
		parent[0][x] = (p < 0) ? x : p;

		for (auto edge: adj[x]){
			int k = edge.to;
			if (k == p) continue;
			dfs(k, x, d + 1, dist + edge.d);
		}

		tout[x] = timer;
	}

	int LCA(int x, int y){
		if (depth[x] > depth[y]) swap(x, y);
		for (int j = lg-1; j >= 0; j--){
			if (depth[y] - (1 << j) >= depth[x]){
				y = parent[j][y];
			}
		}
		if (x == y) return x;
		for (int j = lg-1; j >= 0; j--){
			if (parent[j][x] != parent[j][y]){
				x = parent[j][x];
				y = parent[j][y];
			}
		}
		return parent[0][x];
	}

	// Query variables
	vector<int> reset_queue;
	vector<int> color;
	vector<vector<int>> graph;

	// Query functions
	vector<ll> solve(ll &res, int x, int p = -1){
		vector<ll> mindist(2, inf);
		if (color[x] >= 0) mindist[color[x]] = 0;

		for (auto k: graph[x]){
			if (k == p) continue;
			auto subdist = solve(res, k, x);
			for (int j = 0; j < 2; j++){
				mindist[j] = min(mindist[j], subdist[j] + distance[k] - distance[x]);
			}
		}

		res = min(res, mindist[0] + mindist[1]);
		return mindist;
	}
}

void Init(int N, int A[], int B[], int D[]){
	// Initialize
	n = N;
	lg = 31 - __builtin_clz(n) + 1;
	timer = 0;

	depth.resize(n);
	tin.resize(n);
	tout.resize(n);
	distance.resize(n);
	parent.assign(lg, vector<int>(n));
	adj.resize(n);
	color.assign(n, -1);
	graph.resize(n);

	for (int i = 0; i < n; i++){
		int a = A[i], b = B[i], d = D[i];
		adj[a].push_back(Edge{b, d});
		adj[b].push_back(Edge{a, d});
	}

	// DFS
	dfs(0);
	for (int j = 1; j < lg; j++){
		for (int i = 0; i < n; i++){
			parent[j][i] = parent[j-1][parent[j-1][i]];
		}
	}
}

ll Query(int A, int X[], int B, int Y[]){
	// Construct the virtual tree

	// Find all virtual tree nodes
	vector<int> nodes;

	for (int i = 0; i < A; i++){
		nodes.push_back(X[i]);
		color[X[i]] = 0;
	}

	for (int i = 0; i < B; i++){
		nodes.push_back(Y[i]);
		color[Y[i]] = 1;
	}

	auto sort_by_tin = [&](int p1, int p2){
		return tin[p1] < tin[p2];
	};

	sort(nodes.begin(), nodes.end(), sort_by_tin);
	int sz = nodes.size();

	for (int i = 1; i < sz; i++){
		nodes.push_back(LCA(nodes[i-1], nodes[i]));
	}

	sort(nodes.begin(), nodes.end(), sort_by_tin);
	nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());

	sz = nodes.size();
	for (auto i: nodes) reset_queue.push_back(i);

	// Construct the tree
	stack<int> stk;

	for (int i = 0; i < sz; i++){
		int x = nodes[i];
		while (!stk.empty() && tout[x] > tout[stk.top()]) stk.pop();

		if (!stk.empty()){
			int p = stk.top();
			graph[p].push_back(x);
			graph[x].push_back(p);
		}

		stk.push(x);
	}

	// Solve the query
	ll res = inf;
	solve(res, nodes[0]);

	// Reset
	for (auto x: reset_queue){
		graph[x].clear();
		color[x] = -1;
	}
	reset_queue.clear();

	return res;
}

#undef distance

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