oj.uz

Submission #656600

# Submission time Handle Problem Language Result Execution time Memory
656600 2022-11-08T02:18:11 Z TranGiaHuy1508 Factories (JOI14_factories) C++17
0 / 100
 12 ms 724 KB 
#include <bits/stdc++.h>
using namespace std;

#include "factories.h"

using ll = long long;

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

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

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

			for (int j = 1; j <= _lg; j++){
				for (int 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){
			int j = log2(r - l + 1);
			return min(table[j][l], table[j][r - (1 << j) + 1]);
		}
	};

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

	void euler_dfs(int x, int p = -1, int 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++;
	}

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

	ll distance(int x, int 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);
	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 (int 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<int, int>>(euler_tour);
}

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

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

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

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

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

	stack<int> parent;
	ll res = inf;

	for (int i = 0; i < (int)Z.size(); i++){
		while (!parent.empty()){
			if (tin[parent.top()] <= tin[Z[i]] && tout[Z[i]] <= tout[parent.top()]) break;
			int tp = parent.top(); parent.pop();
			res = min(res, d1[tp] + d2[tp]);
			if (!parent.empty()){
				int 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()){
		int tp = parent.top(); parent.pop();
		res = min(res, d1[tp] + d2[tp]);
		if (!parent.empty()){
			int 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 (int i = 0; i < S; i++) op[X[i]] = 0;
	for (int i = 0; i < T; i++) op[Y[i]] = 0;

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

	return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -