제출 #682766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682766		NK_	공장들 (JOI14_factories)	C++17	100 / 100	3841 ms	204792 KiB

factories

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
#define nl '\n'
 
using ll = long long;
using E = array<int, 2>;
 
const int nax = 5e5+5;
const int LG = 20;
vector<E> adj[nax];
bool vis[nax];
int up[nax][LG];
ll DST[nax][LG];
int par[nax], siz[nax], dep[nax];
ll dx[nax], dy[nax], dst[nax];
 
 
const ll INFL = ll(1e18) + 10;
 
// START OF LCA
 
void dfs(int u = 0, int p = -1) {
	up[u][0] = (p == -1 ? u : p);
	for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];
 
	for(auto e : adj[u]) if (e[0] != p) {
		int v = e[0], w = e[1];
		dst[v] = dst[u] + w;
		dep[v] = dep[u] + 1;
		dfs(v, u);
	}
 
}
 
int jmp(int u, int d) {
	for(int i = 0; i < LG; i++) if ((d>>i) & 1) u = up[u][i];
	return u;
}
 
int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	b = jmp(b, dep[b] - dep[a]); if (a == b) return a;
 
	for(int i = LG - 1; i >= 0; i--) if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
		
	return up[a][0];
}
 
ll dist(int u, int v) {
	return dst[u] + dst[v] - 2LL * dst[lca(u, v)];
}
 
// END OF LCA
 
// START OF CENTROID DECOMPOSITION
int find_size(int u, int p = -1) {
	if (vis[u]) return 0;
	siz[u] = 1;
	for(auto e : adj[u]) if (e[0] != p) {
		int v = e[0];
		siz[u] += find_size(v, u);
	}
	return siz[u];
}
 
int find_centroid(int u, int p, int n) {
	for(auto e : adj[u]) if (e[0] != p) {
		int v = e[0];
		if (!vis[v] && siz[v] > n / 2) return find_centroid(v, u, n);
	}
	return u;
}
 
vector<int> anc;
void init_centroid(int u = 0, int p = -1) {
	find_size(u);
 
	int c = find_centroid(u, -1, siz[u]);
	vis[c] = 1;
	par[c] = p;
 
	for(int i = 0; i < int(size(anc)); i++) {
		int J = int(size(anc)) - i;
		// cout << J << " " << anc[i] << " " << dist(c, anc[i]) << endl;
		DST[c][J] = dist(c, anc[i]);
	}
 
	anc.push_back(c);
 
	for(auto e : adj[c]) {
		int v = e[0];
		if (vis[v]) continue;
		init_centroid(v, c);
	}
	anc.pop_back();
}
// END OF CENTROID DECOMPOSITION
 
 
void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N; i++) {
		vis[i] = 0; par[i] = -1;
		dx[i] = dy[i] = INFL;
		adj[i] = {};
		dst[i] = dep[i] = siz[i] = 0;
 
		for(int j = 0; j < LG; j++) up[i][j] = 0;
	}
 
	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();
	init_centroid();
}
 
vector<int> alt;
ll Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i++) {
		int u = X[i]; 
		dx[u] = 0; alt.push_back(u);
		int jump = 0;
		while(par[u] != -1) {
			u = par[u];
			alt.push_back(u);
			dx[u] = min(dx[u], DST[X[i]][++jump]);
		}
	}

 
	ll ans = INFL;
	for(int i = 0; i < T; i++) {
		int u = Y[i];
		int jump = 0;
		while(u != -1) {
			ans = min(ans, dx[u] + DST[Y[i]][jump++]);
			u = par[u];
		}
	}
 
	for(const auto &u : alt) dx[u] = INFL;
	alt.clear();
 
	return ans;
}

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