Submission #1267427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267427		trvhung	Factories (JOI14_factories)	C++20	100 / 100	7827 ms	461856 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const ll INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
const ll MULTI = 0;
const ld eps = 1e-9;
const ll dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const ll ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const ll nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const ll N = 5e5 + 5;
ll n, ti[N], to[N], et[N], timeDfs;
ll d[N], res;
vector<pair<ll, ll>> adj[N], aux_adj[N];
bool A[N], B[N];

void pre_dfs(ll u, ll p) {
	ti[u] = ++timeDfs;
	et[timeDfs] = u;
	for (auto v: adj[u])
		if (v.F != p)
			pre_dfs(v.F, u);
	to[u] = timeDfs;
}

bool is_ancestor(ll u, ll v) {
	return ti[u] <= ti[v] && ti[v] <= to[u];
}

namespace LCA {
	const ll LOG = 19;
	ll ti[N], et[2 * N], lg2[2 * N], timeDfs = 1, h[N];
	ll d[N];
	pair<ll, ll> st[LOG + 1][2 * N];

	void dfs(ll u, ll p) {
		ti[u] = timeDfs;
		et[timeDfs++] = u;
		for (auto g: adj[u]) {
			ll v = g.F, w = g.S;
			if (v != p) {
				h[v] = h[u] + 1;
				d[v] = d[u] + w;
				dfs(v, u);
				et[timeDfs++] = u;
			}
		}
	}

	void preprocess() {
		lg2[1] = 0;
		for (ll i = 2; i <= 2 * n; ++i) lg2[i] = lg2[i / 2] + 1;
 
		for (ll i = 1; i <= 2 * n; ++i) st[0][i] = make_pair(h[et[i]], et[i]);
		for (ll j = 1; j <= LOG; ++j)
			for (ll i = 1; i + (1 << j) - 1 <= 2 * n; ++i)
				st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
	}

	pair<ll, ll> query(ll l, ll r) {
		ll k = lg2[r - l + 1];
		return min(st[k][l], st[k][r - (1 << k) + 1]);
	}

	ll lca(ll u, ll v) {
		if (ti[u] > ti[v]) swap(u, v);
		return query(ti[u], ti[v]).S;
	}

	ll dist(ll u, ll v) {
		return d[u] + d[v] - 2 * d[lca(u, v)];
	}

	void build() {
		dfs(1, 0);
		preprocess();
	}
}

struct IT {
	ll st[4 * N], lazy[4 * N];

	void build(ll id, ll l, ll r) {
		st[id] = LINF;
		if (l == r) return;

		ll mid = (l + r) >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
	}

	void push(ll id, ll l, ll r) {
		ll &t = lazy[id];
		if (t == 0) return;

		st[id << 1] += t;
		lazy[id << 1] += t;

		st[id << 1 | 1] += t;
		lazy[id << 1 | 1] += t;

		t = 0;
	}

	void updateMass(ll id, ll l, ll r, ll u, ll x) {
		if (l == r) return st[id] = x, void();

		ll mid = (l + r) >> 1; push(id, l, r);
		if (u <= mid) updateMass(id << 1, l, mid, u, x);
		else updateMass(id << 1 | 1, mid + 1, r, u, x);

		st[id] = min(st[id << 1], st[id << 1 | 1]); 
	}

	void update(ll id, ll l, ll r, ll u, ll v, ll x) {
		if (u > v) return;
		if (l == u && r == v) return st[id] += x, lazy[id] += x, void();

		ll mid = (l + r) >> 1; push(id, l, r);
		if (v <= mid) update(id << 1, l, mid, u, v, x);
		else if (u > mid) update(id << 1 | 1, mid + 1, r, u, v, x);
		else {
			update(id << 1, l, mid, u, mid, x);
			update(id << 1 | 1, mid + 1, r, mid + 1, v, x);
		}

		st[id] = min(st[id << 1], st[id << 1 | 1]);
	}
} IT;

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (ll i = 0; i <= n - 2; ++i) {
		A[i]++; B[i]++;
		adj[A[i]].push_back(make_pair(B[i], D[i]));
		adj[B[i]].push_back(make_pair(A[i], D[i]));
	}

	pre_dfs(1, 0);
	LCA::build();
	IT.build(1, 1, n);
}

ll build_auxiliary_tree(vector<ll> &vers) {
	ll sz = (ll) vers.size();

	sort(vers.begin(), vers.end(), [&](ll A, ll B){
		return ti[A] < ti[B];
	});

	for (ll i = 0; i < sz - 1; ++i) {
		ll lca = LCA::lca(vers[i], vers[i + 1]);
		vers.push_back(lca);
	}

	sort(vers.begin(), vers.end(), [&](ll A, ll B){
		return ti[A] < ti[B];
	});

	vers.resize(unique(vers.begin(), vers.end()) - vers.begin());

	vector<ll> stack;
	ll aux_root = vers[0];

	stack.push_back(aux_root);
	for (ll i = 1; i < (ll) vers.size(); ++i) {
		ll u = vers[i];
		while (!stack.empty() && !is_ancestor(stack.back(), u)) 
			stack.pop_back();
		
		assert(!stack.empty());
		ll last = stack.back();
		aux_adj[last].push_back(make_pair(u, LCA::dist(last, u)));
		stack.push_back(u);
	}

	return aux_root;
}

void dfs1(ll u, ll p) {
	for (auto g: aux_adj[u]) {
		ll v = g.F, w = g.S;
		if (v == p) continue;
		d[v] = d[u] + w;
		dfs1(v, u);
	}
}

void dfs2(ll u, ll p) {
	for (auto g: aux_adj[u]) {
		ll v = g.F, w = g.S;
		if (v == p) continue;

		IT.update(1, 1, n, ti[v], to[v], -w);
		IT.update(1, 1, n, 1, ti[v] - 1, w);
		IT.update(1, 1, n, to[v] + 1, n, w);

		if (B[v]) minimize(res, IT.st[1]);
		dfs2(v, u);

		IT.update(1, 1, n, ti[v], to[v], w); 
		IT.update(1, 1, n, 1, ti[v] - 1, -w);
		IT.update(1, 1, n, to[v] + 1, n, -w);
	}
}
	
ll Query(int S, int X[], int T, int Y[]) {
	vector<ll> vers;
	for (ll i = 0; i < S; ++i) {
		A[++X[i]] = 1;
		vers.push_back(X[i]);
	}
	for (ll i = 0; i < T; ++i) {
		B[++Y[i]] = 1;
		vers.push_back(Y[i]);
	}

	ll root = build_auxiliary_tree(vers);
	dfs1(root, 0);

	for (ll i = 0; i < S; ++i) IT.updateMass(1, 1, n, ti[X[i]], d[X[i]]);
	res = (B[root] ? IT.st[1] : LINF);
	dfs2(root, 0);

	for (auto x: vers) aux_adj[x].clear(), d[x] = 0;
	for (ll i = 0; i < S; ++i) {
		IT.updateMass(1, 1, n, ti[X[i]], LINF);
		A[X[i]] = 0;
	}
	for (ll i = 0; i < T; ++i) B[Y[i]] = 0;

	return res;
}

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