제출 #793920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793920		acatmeowmeow	공장들 (JOI14_factories)	C++11	100 / 100	5376 ms	345464 KiB

factories

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

using namespace std;

#define int long long 

const int NMAX = 5e5, KMAX = 20;
int par[NMAX + 5], sz[NMAX + 5], d[NMAX + 5], h[NMAX + 5], root[NMAX + 5], rootCentroid, ans[NMAX + 5], cnt[NMAX + 5], cur = 0;
int tin[NMAX + 5], euler[2*NMAX + 5], table[2*NMAX + 5][KMAX + 5], lg[2*NMAX + 5], timer = -1;
bool vis[NMAX + 5];
vector<pair<int, int>> adj[NMAX + 5];

void dfs(int u, int e) {
	tin[u] = ++timer;
	euler[timer] = u;
	for (auto&x : adj[u]) {
		int v = x.first, c = x.second;
		if (v == e) continue;
		d[v] = d[u] + c, h[v] = h[u] + 1;
	   	dfs(v, u);	
		euler[++timer] = u;
	}
}

int combine(int x, int y) { return h[x] < h[y] ? x : y; }

void buildTable(int n) {
	lg[1] = 0;
	for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
	for (int i = 0; i < n; i++) table[i][0] = euler[i];
	for (int j = 1; j < KMAX; j++) {
		for (int i = 0; i + (1ll << j) - 1 < n; i++) {
			table[i][j] = combine(table[i][j - 1], table[i + (1ll << (j - 1))][j - 1]);
		}
	}
}

int lca(int u, int v) {
	if (tin[u] > tin[v]) swap(u, v);
	int k = lg[tin[v] - tin[u] + 1];
	return combine(table[tin[u]][k], table[tin[v] - (1ll << k) + 1][k]);
}

int getDistance(int u, int v) {
	int w = lca(u, v);
	return d[u] + d[v] - 2*d[w];
}

void dfs2(int u, int e) {
	sz[u] = 1;
	for (auto&x : adj[u]) {
		int v = x.first;
		if (v == e || vis[v]) continue;
		dfs2(v, u);
		sz[u] += sz[v];
	}
}

int findCentroid(int u, int e, int S) {
	for (auto&x : adj[u]) {
		int v = x.first;
		if (v == e || vis[v] || sz[v] <= S/2) continue;
		return findCentroid(v, u, S);
	}
	return u;
}

int buildCentroid(int u) {
	dfs2(u, -1);
	int curCentroid = findCentroid(u, -1, sz[u]);	
	vis[curCentroid] = true;
	for (auto&x : adj[curCentroid]) {
		int v = x.first;
		if (vis[v]) continue;
		int nextCentroid = buildCentroid(v);
		root[nextCentroid] = curCentroid;
	}
	return curCentroid;
}

void Init(signed N, signed A[], signed B[], signed D[]) {
	for (int i = 0; i < N - 1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, -1);
	buildTable(2*N);
	rootCentroid = buildCentroid(0);
	root[rootCentroid] = -1;
}

long long Query(signed S, signed X[], signed T, signed Y[]) {
	cur++;
	for (int i = 0; i < T; i++) {
		for (int j = Y[i]; j != -1; j = root[j]) {
			if (cnt[j] != cur) ans[j] = 1e18;
			ans[j] = min(ans[j], getDistance(Y[i], j));
			cnt[j] = cur;
		}
	}
	int res = 1e18;
	for (int i = 0; i < S; i++) {
		for (int j = X[i]; j != -1; j = root[j]) {
			if (cnt[j] != cur) continue;
			res = min(res, getDistance(X[i], j) + ans[j]);	
		}
	}
	return res;
}

/*signed main() {
	signed N, Q;
	cin >> N >> Q;
	signed A[N], B[N], D[N];
	for (int i = 0; i < N - 1; i++) cin >> A[i] >> B[i] >> D[i];
	Init(N, A, B, D);
	for (int i = 0; i < Q; i++) {
		int S, T;
		cin >> S >> T;
		signed X[S], Y[T];
		for (int j = 0; j < S; j++) cin >> X[j];
		for (int j = 0; j < T; j++) cin >> Y[j];
		cout << Query(S, X, T, Y) << '\n';
	}
	return 0;
}*/

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