Submission #1255986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255986		pasta	Factories (JOI14_factories)	C++20	0 / 100	27 ms	47680 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, ll> pii;



#define pb		push_back
#define all(x)	x.begin(), x.end()
// #define int ll
// #define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll inf = 1e18 + 10;
const int maxn = 1e6 + 10;

ll dist[maxn], sub[maxn];
vector<pii> G[maxn], cent[maxn];
bool dead[maxn];

int dfs_sz(int v, int p) {
	sub[v] = 1;
	for (auto [u, w] : G[v]) {
		if (u == p || dead[u]) continue;
		sub[v] += dfs_sz(u, v);
	}
	return sub[v];
}

int centroid(int v, int p, int sz) {
	for (auto [u, w] : G[v]) {
		if (u == p || dead[u]) continue;
		if (sz < sub[u] * 2)
			return centroid(u, v, sz);
	}
	return v;
}

void add(int v, int p, int tag, int d = 0) {
	cent[v].pb({tag, d});
	for (auto [u, w] : G[v]) {
		if (u == p || dead[u]) continue;
		add(u, v, tag, d + w);
	}
}

void decomp(int v) {
	int cen = centroid(v, 0, dfs_sz(v, 0));
	add(cen, 0, cen);
	for (auto [u, w] : G[v]) {
		if (dead[u]) continue;
		decomp(u);
	}
}


void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N - 1; i++) {
		G[A[i]].pb({B[i], D[i]});
		G[B[i]].pb({A[i], D[i]});
	}
}

ll Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) {
		for (auto [u, d] : cent[X[i]]) {
			dist[u] = inf;
		}
	}

	for (int i = 0; i < T; i++) {
		for (auto [u, d] : cent[Y[i]]) {
			dist[u] = min(dist[u], d);
		}
	}

	ll ans = inf;
	for (int i = 0; i < S; i++) {
		for (auto [u, d] : cent[X[i]]) {
			ans = min(ans, d + dist[u]);
		}
	}
	return ans;
}

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