Submission #25539

#	Time	Username	Problem	Language	Result	Execution time	Memory
25539		khsoo01	Factories (JOI14_factories)	C++11	15 / 100	6000 ms	211652 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e18, N = 500005, L = 20;

ll n, s[N], e[N], inv[N], dep[N], frd[N];
ll par[L][N], dt[3][N], typ[N], cc, ans;

vector<pll> adj[N], tmp[N];

void calc (ll C, ll P) {
	s[C] = ++cc;
	inv[cc] = C;
	for(auto &T : adj[C]) {
		ll A, B; tie(A, B) = T;
		if(A == P) continue;
		par[0][A] = C;
		frd[A] = frd[C] + B;
		dep[A] = dep[C] + 1;
		calc(A, C);
	}
	e[C] = cc;
}

ll getlca (ll A, ll B) {
	if(dep[A] < dep[B]) swap(A, B);
	for(ll i=L;i--;) {
		if(dep[A] - dep[B] >= (1<<i)) {
			A = par[i][A];
		}
	}
	if(A == B) return A;
	for(ll i=L;i--;) {
		if(par[i][A] != par[i][B]) {
			A = par[i][A]; B = par[i][B];
		}
	}
	return par[0][A];
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(ll i=0;i<n-1;i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	calc(0, 0);
	for(ll k=1;k<L;k++) {
		for(ll i=0;i<n;i++) {
			par[k][i] = par[k-1][par[k-1][i]];
		}
	}
}

void dfs (ll C, ll P) {
	dt[1][C] = dt[2][C] = inf;
	dt[typ[C]][C] = 0;
	for(auto &T : tmp[C]) {
		ll A, B; tie(A, B) = T;
		if(A == P) continue;
		dfs(A, C);
		dt[1][C] = min(dt[1][C], dt[1][A] + B);
		dt[2][C] = min(dt[2][C], dt[2][A] + B);
	}
	ans = min(ans, dt[1][C]+dt[2][C]);
}

ll Query(int C1, int X[], int C2, int Y[]) {
	vector<ll> V, S;
	for(ll i=0;i<C1;i++) {
		V.push_back(s[X[i]]);
		typ[X[i]] = 1;
	}
	for(ll i=0;i<C2;i++) {
		V.push_back(s[Y[i]]);
		typ[Y[i]] = 2;
	}
	sort(V.begin(), V.end());
	for(ll i=1;i<C1+C2;i++) {
		ll A = inv[V[i-1]], B = inv[V[i]];
		V.push_back(s[getlca(A, B)]);
	}
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	for(auto &T : V) tmp[inv[T]].clear();
	for(auto &T : V) {
		ll A = inv[T];
		while(!S.empty()) {
			ll P = S.back();
			if(s[P] <= s[A] && e[A] <= e[P]) break;
			else S.pop_back();
		}
		if(!S.empty()) {
			ll P = S.back(), D = frd[A] - frd[P];
			tmp[A].push_back({P, D});
			tmp[P].push_back({A, D});
		}
		S.push_back(A);
	}
	ans = inf;
	dfs(inv[V[0]], inv[V[0]]);
	for(auto &T : V) typ[inv[T]] = 0;
	return ans;
}

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