Submission #529326

#	Time	Username	Problem	Language	Result	Execution time	Memory
529326		LucaDantas	Factories (JOI14_factories)	C++17	15 / 100	8058 ms	229880 KiB

factories

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

#define int long long

constexpr int maxn = 5e5+10, logn = 22;
constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

vector<pair<int,int>> g[maxn];

int in[maxn], pai[logn][maxn], profundidade[maxn], t, n;
long long depth[maxn];

void dfs(int u) {
	in[u] = ++t;
	for(auto [v, w] : g[u])
		if(v != pai[0][u])
			pai[0][v] = u, depth[v] = depth[u] + w, profundidade[v] = profundidade[u] + 1, dfs(v);
}

void build_binary_lifting() {
	for(int l = 1; l < logn; l++) {
		for(int i = 1; i < maxn; i++) {
			pai[l][i] = pai[l-1][pai[l-1][i]];
		}
	}
}

int LCA(int a, int b) {
	if(profundidade[a] < profundidade[b]) swap(a, b);
	for(int l = logn-1; l >= 0; l--) {
		if(profundidade[a] - (1 << l) >= profundidade[b])
			a = pai[l][a];
	}
	if(a == b) return a;
	for(int l = logn-1; l >= 0; l--) {
		if(pai[l][a] != pai[l][b])
			a = pai[l][a], b = pai[l][b];
	}
	return pai[0][a];
}

long long dist(int a, int b) { return depth[a] + depth[b] - 2*depth[LCA(a, b)]; }

vector<pair<int, long long>> vt[maxn];

vector<int> get_vt(vector<int> v) {
	sort(v.begin(), v.end(), [](int a, int b) { return in[a] < in[b]; });
	v.erase(unique(v.begin(), v.end()), v.end());
	
	int tam = v.size();
	for(int i = 1; i < tam; i++)
		v.push_back(LCA(v[i-1], v[i]));

	sort(v.begin(), v.end(), [](int a, int b) { return in[a] < in[b]; });
	v.erase(unique(v.begin(), v.end()), v.end());
	
	for(int x : v)
		vt[x].clear();

	for(int i = 1; i < v.size(); i++) {
		int lca = LCA(v[i-1], v[i]);
		long long DIST = dist(v[i], lca);
		vt[lca].push_back({v[i], DIST});
		vt[v[i]].push_back({lca, DIST});
	}

	return v;

	// DEBUG
	/* puts("VIRTUAL TREE");
	for(int x : v)
		printf("%d ", x);
	puts("");

	return v; */
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
	n = N;
	for(int i = 0; i < n-1; i++) {
		A[i]++, B[i]++;
		g[A[i]].push_back({B[i], D[i]}), g[B[i]].push_back({A[i], D[i]});
	}
	profundidade[1] = 1;
	depth[1] = 1;
	dfs(1);
	build_binary_lifting();
}

long long dd[maxn];
bool mark[maxn];

long long dijkstra(vector<int> tudo, vector<int> X, vector<int> Y) {
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
	for(int x : tudo)
		dd[x] = inf, mark[x] = 0;
	for(int x : Y)
		dd[x] = 0, q.push({0, x});

	while(q.size()) {
		int u = q.top().second;
		q.pop();
		if(mark[u]) continue;
		mark[u] = 1;

		for(auto [v, w] : vt[u])
			if(dd[v] > dd[u] + w)
				dd[v] = dd[u] + w, q.push({dd[v], v});
	}

	long long ans = inf;
	for(int x : X)
		ans = min(ans, dd[x]);
	return ans;
}

long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
	vector<int> v, x, y;
	for(int i = 0; i < S; i++)
		v.push_back(X[i]+1), x.push_back(X[i]+1);
	for(int i = 0; i < T; i++)
		v.push_back(Y[i]+1), y.push_back(Y[i]+1);
	return dijkstra(get_vt(v), x, y);
}

Compilation message (stderr)

factories.cpp: In function 'std::vector<long long int> get_vt(std::vector<long long int>)':
factories.cpp:62:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 1; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~

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