제출 #364334

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

factories

#include "factories.h"
#include <bits/stdc++.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] ];
}

long long Query(int S, int X[], int T, int Y[]) {
	ll res = inf;
	for (int i = 0;i < S;++i)
		for (int j = 0;j < T;++j) {
			int a = X[i], b = Y[j];
			chmin(res, dep[a] + dep[b] - 2 * dep[getlca(a, b)]);
		}
	return res;
}

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