Submission #1269382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269382		thieunguyenhuy	Factories (JOI14_factories)	C++20	100 / 100	1866 ms	148724 KiB

factories

#ifndef hwe
	#include "factories.h"
#endif

#include <bits/stdc++.h>
using namespace std;

#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2> bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T> void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long random(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);
}
unsigned long long random(unsigned long long l, unsigned long long r) {
    return uniform_int_distribution<unsigned long long>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 5e5 + 5, LG = 20;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

int dfsTime = 0;
ll ans = INF;
int dep[N], up[N][LG], mark[N], tin[N], tout[N], minX[N], minY[N];
ll dist[N];
vii adj[N];
vector<int> ke[N];

void dfs(int u, int fa) {
	tin[u] = ++dfsTime;
	for (auto [v, w] : adj[u]) if (v != fa) {
		dist[v] = dist[u] + w, dep[v] = dep[u] + 1;
		up[v][0] = u;
		for (int i = 1; i < LG; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
		dfs(v, u);
	}
	tout[u] = dfsTime;
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	int delta = dep[u] - dep[v];
	for (int i = 0; MASK(i) <= delta; ++i) if (BIT(delta, i)) {
		u = up[u][i];
	}
	if (u == v) return u;
	for (int i = LOG(dep[u]); i >= 0; --i) if (up[u][i] != up[v][i]) {
		u = up[u][i], v = up[v][i];
	}
	return up[u][0];
}

void Init(int n, int A[], int B[], int D[]) {
	for (int i = 0; i < n; ++i) adj[i].clear();

	for (int i = 0; i < n - 1; ++i) {
		int u = A[i], v = B[i], w = D[i];
		adj[u].emplace_back(v, w), adj[v].emplace_back(u, w);
	}

	dfs(0, -1);
}

void traverse(int u) {
	// cerr << "u = " << u << '\n';

	if (mark[u] == 1) minX[u] = u;
	if (mark[u] == 2) minY[u] = u;

	for (auto v : ke[u]) {
		traverse(v);
		if (minX[u] != -1 && minY[v] != -1)
			minimize(ans, dist[minX[u]] + dist[minY[v]] - 2 * dist[u]);
		if (minY[u] != -1 && minX[v] != -1)
			minimize(ans, dist[minY[u]] + dist[minX[v]] - 2 * dist[u]);
		if (minX[u] == -1 || (minX[v] != -1 && dist[minX[u]] > dist[minX[v]])) minX[u] = minX[v];
		if (minY[u] == -1 || (minY[v] != -1 && dist[minY[u]] > dist[minY[v]])) minY[u] = minY[v];
	}
}

ll Query(int S, int X[], int T, int Y[]) {
	vector<int> ve;
	for (int i = 0; i < S; ++i) ve.emplace_back(X[i]);
	for (int i = 0; i < T; ++i) ve.emplace_back(Y[i]);

	auto cmp = [&](int u, int v) {
		return tin[u] < tin[v];
	};

	sort (ve.begin(), ve.end(), cmp);
	for (int i = 0; i + 1 < S + T; ++i)
		ve.emplace_back(lca(ve[i], ve[i + 1]));

	for (auto &x : ve) {
		mark[x] = 0, ke[x].clear();
		minX[x] = minY[x] = -1;
	}
	for (int i = 0; i < S; ++i) mark[X[i]] = 1;
	for (int i = 0; i < T; ++i) mark[Y[i]] = 2;

	// cerr << "Nguyen\n";

	remove_duplicate(ve);
	sort (ve.begin(), ve.end(), cmp);
	stack<int> st;

	for (int i = 0; i < ve.size(); ++i) {
		while (!st.empty() && tin[ve[i]] > tout[st.top()]) st.pop();
		if (!st.empty()) ke[st.top()].emplace_back(ve[i]);
		st.emplace(ve[i]); 
	}

	// cerr << "Stella\n";

	int root = ve[0];
	ans = INF; traverse(root);
	return ans;
}

#ifdef hwe
int A[N], B[N], D[N], X[N], Y[N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n, q; cin >> n >> q;

    for (int i = 0; i < n - 1; ++i) {
    	cin >> A[i] >> B[i] >> D[i];
    }

    Init(n, A, B, D);

    for (int i = 1; i <= q; ++i) {
    	int S, T; cin >> S >> T;
    	for (int j = 0; j < S; ++j) cin >> X[j];
    	for (int j = 0; j < T; ++j) cin >> Y[j];
    	cout << Query(S, X, T, Y) << '\n';
    }

    return 0;
}
#endif

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