Submission #682761

#	Time	Username	Problem	Language	Result	Execution time	Memory
682761		NK_	Factories (JOI14_factories)	C++17	100 / 100	5310 ms	217756 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;
vector<E> adj[nax];
bool vis[nax];
vector<ll> dst[nax];
int par[nax], siz[nax];
ll dx[nax];


const ll INFL = ll(1e18) + 10;

// 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]) {
		auto [v, w] = e; 
		if (v == p) continue;
		siz[u] += find_size(v, u);
	}
	return siz[u];
}

int find_centroid(int u, int p, int n) {
	for(auto e : adj[u]) {
		auto [v, w] = e;
		if (v == p) continue;
		if (!vis[v] && siz[v] > n / 2) return find_centroid(v, u, n);
	}
	return u;
}

void dfs2(int u, int p = -1) {
	for(auto e : adj[u]) {
		auto [v, w] = e; 
		if (v == p || vis[v]) continue;
		dst[v].push_back(dst[u].back() + w);
		dfs2(v, u);
	}
}

void init_centroid(int u = 0, int p = -1) {
	find_size(u);

	int c = find_centroid(u, -1, siz[u]);
	
	dst[c].push_back(0);
	dfs2(c);
	
	vis[c] = 1;
	par[c] = p;

	for(auto e : adj[c]) {
		auto [v, wv] = e;
		if (vis[v]) continue;
		init_centroid(v, c);
	}

}
// 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] = INFL;
		adj[i] = {};
		siz[i] = 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]});
	}

	init_centroid();

	for(int i = 0; i < N; i++) reverse(begin(dst[i]), end(dst[i]));
}

ll Query(int S, int X[], int T, int Y[]) {
	vector<int> alt;
	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];
		}
	}

	sort(begin(alt), end(alt)); alt.erase(unique(begin(alt), end(alt)), end(alt));

	for(auto u : alt) dx[u] = INFL;

	return ans;
}

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