Submission #529322

#	Time	Username	Problem	Language	Result	Execution time	Memory
529322		LucaDantas	Factories (JOI14_factories)	C++17	0 / 100	88 ms	106384 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], 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, 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(depth[a] < depth[b]) swap(a, b);
	for(int l = logn-1; l >= 0; l--) {
		if(depth[pai[l][a]] >= depth[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]; });
	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 = depth[v[i]] - depth[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(""); */
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
	n = N;
	for(int i = 0; i < n; i++) {
		A[i]++, B[i]++;
		g[A[i]].push_back({B[i], D[i]}), g[B[i]].push_back({A[i], D[i]});
	}
	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] : g[u])
		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);

	vector<int> tudo(n);
	for(int i = 0; i < n; i++)
		tudo[i] = i+1;

	get_vt(v);
	
	return dijkstra(tudo, x, y);
}

Compilation message (stderr)

factories.cpp: In function 'std::vector<long long int> get_vt(std::vector<long long int>)':
factories.cpp:59: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]
   59 |  for(int i = 1; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~

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