제출 #364339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364339		Kevin_Zhang_TW	공장들 (JOI14_factories)	C++17	100 / 100	7120 ms	117052 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) {  cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 500010, LG = 19;
const ll inf = 1ll << 55;

ll dep[MAX_N];
int anc[LG][MAX_N], in[MAX_N], out[MAX_N], n;
vector<pair<int,int>> edge[MAX_N];

void dfs1(int x, int lst) {
	static int t;
	in[x] = ++t;
	for (auto [u, w] : edge[x]) if (u != lst) {
		anc[0][u] = x;
		dep[u] = dep[x] + w;
		dfs1(u, x);
	}
	out[x] = t;
}
bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
int getlca(int a, int b) { 
	for (int d = LG-1;d >= 0;--d)
		if (!isanc(anc[d][a], b))
			a = anc[d][a];
	return isanc(a, b) ? a : anc[0][a];
}
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0;i < N-1;++i) {
		int a = A[i], b = B[i], c = D[i];
		edge[a].pb(b, c);
		edge[b].pb(a, c);
	}
	dfs1(0, 0);
	for (int d = 1;d < LG;++d)
		for (int i = 0;i < N;++i)
			anc[d][i] = anc[d-1][ anc[d-1][i] ];
}
struct conf {
	int vis[MAX_N], time;
	void reset() { ++time; }
	void insert(int i) { vis[i] = time; }
	int count(int i) { return vis[i] == time; }
}svis, tvis;

long long Query(int S, int X[], int T, int Y[]) {
	ll res = inf;
	svis.reset(), tvis.reset();
	for (int i = 0;i < S;++i)
		svis.insert(X[i]);
	for (int i = 0;i < T;++i)
		tvis.insert(Y[i]);

	vector<int> loc(X, X+S); loc.insert(end(loc), Y, Y+T);
	sort(AI(loc), [&](int a, int b) { 
			return in[a] < in[b]; });
	loc.resize(unique(AI(loc)) - begin(loc));

	{
		int os = loc.size();
		for (int i = 0;i + 1 < os;++i) 
			loc.pb(getlca(loc[i], loc[i+1]));
	}

	sort(AI(loc), [&](int a, int b) { 
			return in[a] < in[b]; });
	loc.resize(unique(AI(loc)) - begin(loc));

	vector<int> stk;
	vector<pair<ll,ll>> dp;

	auto update = [&](int a, int b) {
		auto &[a0, a1] = dp[a];
		auto &[b0, b1] = dp[b];
		chmin(res, a0 + b1 - 2 * dep[stk[a]]);
		chmin(res, a1 + b0 - 2 * dep[stk[a]]);
		chmin(a0, b0), chmin(a1, b1);
	};
//	DE(S), debug(X, X+S);
//	DE(T), debug(Y, Y+T);
	for (int x : loc) {
		while (stk.size() > 1) {
			if (isanc(stk.back(), x)) break;
			update(stk.size() - 2, stk.size() - 1);
			stk.pop_back(), dp.pop_back();
		}
		stk.pb(x);
		dp.pb(inf, inf);
		if (svis.count(x)) dp.back().first = dep[x];
		if (tvis.count(x)) dp.back().second = dep[x];
		//DE(x, dp.back().first, dp.back().second, svis.count(x), tvis.count(x));

	}
	while (stk.size() > 1) {
		update(stk.size() - 2, stk.size() - 1);
		stk.pop_back(), dp.pop_back();
	}
	return res;
}

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