Submission #642965

#	Time	Username	Problem	Language	Result	Execution time	Memory
642965		ymm	Factories (JOI14_factories)	C++17	33 / 100	8096 ms	185144 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 510'010;
const int lg = 19;
vector<pll> A[N];
int anc[N][lg];
int h[N];
ll dis[N][lg];
int n;

void dfs(int v, int p, ll w, int h)
{
	::h[v] = h;
	anc[v][0] = p;
	dis[v][0] = w;
	Loop (i,0,lg-1) {
		anc[v][i+1] = anc[anc[v][i]][i];
		dis[v][i+1] = dis[v][i] + dis[anc[v][i]][i];
	}
	for (auto [u, w] : A[v]) {
		if (u != p)
			dfs(u, v, w, h+1);
	}
}

ll get_dis(int v, int u)
{
	if (h[v] < h[u])
		swap(v, u);
	ll ans = 0;
	int diff = h[v] - h[u];
	Loop (i,0,lg) {
		if (diff & (1<<i)) {
			ans += dis[v][i];
			v = anc[v][i];
		}
	}
	if (v == u)
		return ans;
	LoopR (i,0,lg) {
		if (anc[v][i] != anc[u][i]) {
			ans += dis[v][i];
			ans += dis[u][i];
			v = anc[v][i];
			u = anc[u][i];
		}
	}
	return ans + dis[v][0] + dis[u][0];
}

void Init(int N, int X[], int Y[], int D[])
{
	n = N;
	Loop (i,0,n) {
		A[X[i]].push_back({Y[i],D[i]});
		A[Y[i]].push_back({X[i],D[i]});
	}
	dfs(0, 0, 0, 0);
}

ll dij(int s, int x[], int t, int y[])
{
	static ll dis[N];
	fill(dis, dis+N, (ll)1e18);
	priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
	Loop (i,0,s) {
		dis[x[i]] = 0;
		q.push({0,x[i]});
	}
	while (q.size()) {
		auto [d, v] = q.top();
		q.pop();
		if (d != dis[v])
			continue;
		for (auto [u, w] : A[v]) {
			if (d + w < dis[u]) {
				dis[u] = d + w;
				q.push({dis[u], u});
			}
		}
	}
	ll ans = 1e18;
	Loop (i,0,t)
		ans = min(ans, dis[y[i]]);
	return ans;
}

long long Query(int S, int X[], int T, int Y[])
{
	if ((ll)S * T <= n) {
		ll ans = 1e18;
		Loop (i,0,S) Loop (j,0,T)
			ans = min(ans, get_dis(X[i], Y[j]));
		return ans;
	} else {
		return dij(S, X, T, Y);
	}
}

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