Submission #467065

#	Time	Username	Problem	Language	Result	Execution time	Memory
467065		Namnamseo	Factories (JOI14_factories)	C++17	100 / 100	4139 ms	178504 KiB

factories

#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
using pp=pair<int,int>;
using ll=long long;
const int maxn = int(5e5) + 10;
const ll inf = (1ll<<60);

int n, q;
vector<pp> e[maxn];

int tin[maxn], tout[maxn], nt;
int par[20][maxn];
int dep[maxn];
ll dd[maxn];

void dfs(int x) {
	tin[x] = ++nt;
	for (auto tmp:e[x]) {
		int y, d; tie(y, d) = tmp;
		if (y == par[0][x]) continue;
		par[0][y] = x;
		dep[y] = dep[x]+1;
		dd[y] = dd[x] + d;
		dfs(y);
	}
	tout[x] = nt;
}

int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	for (int df=dep[b]-dep[a], i=18; 0<=i; --i)
		if (1&(df>>i)) b = par[i][b];
	if (a == b) return a;
	for (int i=18; 0<=i; --i) if (par[i][a] != par[i][b])
		a = par[i][a], b = par[i][b];
	return par[0][a];
}

vector<int> vx, vy;
vector<int> va;

bitset<maxn> isx;
bitset<maxn> isy;
vector<pair<int,ll>> te[maxn];
ll dx[maxn], dy[maxn];

pair<ll,ll> tdfs(int x, pair<ll,ll> pd) {
	if (isx[x]) pd.first = 0;
	else if (isy[x]) pd.second = 0;
	ll cx = inf, cy = inf;
	for (auto tmp : te[x]) {
		int y; ll d; tie(y, d) = tmp;
		ll ccx, ccy; tie(ccx, ccy) = tdfs(y, {pd.first+d, pd.second+d});
		cx = min(cx, ccx+d);
		cy = min(cy, ccy+d);
	}
	dx[x] = min(cx, pd.first);
	dy[x] = min(cy, pd.second);
	if (isx[x]) cx = 0;
	else if (isy[x]) cy = 0;
	return {cx, cy};
}

void Init(int n, int A[], int B[], int D[]) {
	for (int i=0; i<n-1; ++i) {
		e[A[i]+1].emplace_back(B[i]+1, D[i]);
		e[B[i]+1].emplace_back(A[i]+1, D[i]);
	}
	dfs(1);
	for (int i=1; i<=18; ++i) for (int j=1; j<=n; ++j) {
		par[i][j] = par[i-1][par[i-1][j]];
	}
}

ll Query(int nx, int X[], int ny, int Y[]) {
    vx.clear(); vx.insert(vx.end(), X, X+nx); for (int &x:vx) ++x;
    vy.clear(); vy.insert(vy.end(), Y, Y+ny); for (int &y:vy) ++y;

	va.resize(nx + ny);
	copy(vx.begin(), vx.end(), va.begin());
	copy(vy.begin(), vy.end(), va.begin()+nx);
	sort(va.begin(), va.end(), [&](const int& a, const int& b) {
		return tin[a] < tin[b];
	});
	for (int i=0; i+1<nx+ny; ++i) {
		int a = va[i], b = va[i+1], l = lca(a, b);
		if (l != a && l != b) va.push_back(l);
	}
	sort(va.begin(), va.end(), [&](const int& a, const int& b) {
		return tin[a] < tin[b];
	});
	va.erase(unique(va.begin(), va.end()), va.end());

	static vector<int> stk; stk.clear();
	for (int x : va) {
		while (!stk.empty()) {
			int p = stk.back();
			if (tin[p] <= tin[x] && tin[x] <= tout[p]) break;
			stk.pop_back();
		}
		if (!stk.empty()) {
			int p = stk.back();
			te[p].emplace_back(x, dd[x]-dd[p]);
		}
		stk.push_back(x);
	}
	for (int x : vx) isx.set(x);
	for (int y : vy) isy.set(y);

	tdfs(va[0], {inf, inf});
	ll ans = inf;
	for (int a : va) ans = min(ans, dx[a]+dy[a]);

	for (int x : va) te[x].clear();
	for (int x : vx) isx.reset(x);
	for (int y : vy) isy.reset(y);

    return ans;
}

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