Submission #1256004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256004		pasta	공장들 (JOI14_factories)	C++20	0 / 100	2618 ms	292028 KiB

factories

#include <bits/stdc++.h>
#include "factories.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) {
	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, -1, dfs_sz(v, -1));
	add(cen, 0, cen, 0);
	dead[cen] = 1;
	for (auto [u, w] : G[cen]) {
		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]});
	}
	decomp(0);
}

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;
}


// int main() {
// 	int n, q;
// 	cin >> n >> q;
// 	int a[n + 1], b[n + 1], d[n + 1];
// 	for (int i = 0; i < n - 1; i++) {
// 		cin >> a[i] >> b[i] >> d[i];
// 	}
// 	Init(n, a, b, d);
// 	while (q--) {
// 		int s, t;
// 		cin >> s >> t;
// 		int S[s + 1], T[t + 1];
// 		for (int i = 0; i < s; i++)
// 			cin >> S[i];
// 		for (int i = 0; i < t; i++)
// 			cin >> T[i];
// 		cout << Query(s, S, t, T) << '\n';
// 	}
// }

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