Submission #255757

#	Time	Username	Problem	Language	Result	Execution time	Memory
255757		islingr	Factories (JOI14_factories)	C++17	100 / 100	7913 ms	150712 KiB

factories

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a); )
#define sz(x...) int((x).size())
#define all(x) begin(x), end(x)
#define eb(x...) emplace_back(x)
#define lb(x...) lower_bound(x)

template<class T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

using ll = int64_t;

const ll inf = 1e18;
const int B = 19, N = 1 << B;
int dep[N], p[N][B], in[N];
ll dist[N];

void Init(int n, int a[], int b[], int d[]) {
	vector<vector<int>> g(n);
	rep(e, 0, n - 1) g[a[e]].eb(e), g[b[e]].eb(e);
	int timer = 0;
	function<void(int)> dfs = [&](int u) {
		in[u] = timer++;
		for (int e : g[u]) {
			int v = u != a[e] ? a[e] : b[e];
			if (v == p[u][0]) continue;
			dist[v] = dist[u] + d[e];
			dep[v] = dep[u] + 1;
			p[v][0] = u;
			rep(j, 0, B - 1) p[v][j + 1] = p[p[v][j]][j];
			dfs(v);
		}
	};
	dfs(0);
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	per(j, 0, B) if (dep[v] <= dep[p[u][j]]) u = p[u][j];
	if (u == v) return u;
	per(j, 0, B) if (p[u][j] != p[v][j]) u = p[u][j], v = p[v][j];
	return p[u][0];
}

vector<int> g[N];
short col[N];
ll s[N], t[N];

ll Query(int S, int X[], int T, int Y[]) {
	vector<int> V; V.reserve(S + T);
	rep(i, 0, S) col[X[i]] = +1, V.eb(X[i]);
	rep(i, 0, T) col[Y[i]] = -1, V.eb(Y[i]);
	sort(all(V), [&](int x, int y) { return in[x] < in[y]; });
	rep(i, 1, S + T) V.eb(lca(V[i - 1], V[i]));
	sort(all(V), [&](int x, int y) { return in[x] < in[y]; });
	V.erase(unique(all(V)), end(V));
	rep(i, 1, sz(V)) g[lca(V[i - 1], V[i])].eb(V[i]);
	ll ans = inf;
	function<void(int)> dfs = [&](int u) {
		s[u] = t[u] = inf;
		if (col[u] > 0) s[u] = 0;
		if (col[u] < 0) t[u] = 0;
		for (int v : g[u]) {
			dfs(v);
			ckmin(s[u], dist[v] - dist[u] + s[v]);
			ckmin(t[u], dist[v] - dist[u] + t[v]);
		}
		ckmin(ans, s[u] + t[u]);
	};
	dfs(V[0]);
	for (int v : V) g[v].clear(), col[v] = 0;
	return ans;
}

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