Submission #1234588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234588		antromancap	Factories (JOI14_factories)	C++20	100 / 100	1326 ms	195168 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 1, LOG = 20;
int n, st[2 * N][LOG], pos[N], h[N], num[N], tail[N], cnt = 0, timeDfs = 0;
long long d[N];
vector<pair<int, int>> adj[N];
vector<int> adj2[N];

void dfs(int u, int p) {
	st[++cnt][0] = u;
	pos[u] = cnt;
	num[u] = ++timeDfs;
	for (auto [v, w] : adj[u]) {
		if (v == p) continue;
		d[v] = d[u] + w;
		h[v] = h[u] + 1;
		dfs(v, u);
		st[++cnt][0] = u;
	}
	tail[u] = timeDfs;
}

#define minHigh(u, v) (h[u] < h[v] ? u : v)
int lck(int u, int v) {
	u = pos[u], v = pos[v];
	if (u > v) swap(u, v);
	int k = __lg(v - u + 1);
	return minHigh(st[u][k], st[v - (1 << k) + 1][k]);
}

void Init(int _N, int A[], int B[], int D[]) {
	::n = _N;
	for (int i = 0; i < n - 1; i++) {
		A[i]++, B[i]++;
		adj[A[i]].push_back({ B[i], D[i] });
		adj[B[i]].push_back({ A[i], D[i] });
	}
	dfs(1, 1);
	for (int k = 1; 1 << k <= cnt; k++)
		for (int i = 1; i + (1 << k) - 1 <= cnt; i++) st[i][k] = minHigh(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}

const long long inf = 1e18;
long long res = 0, dp[N][2];
int x[N], mark[N], col[N], cur = 0, sz = 0;
void process(int u) {
	if (col[u] == 1) dp[u][0] = 0;
	if (col[u] == 2) dp[u][1] = 0;
	for (int v : adj2[u]) {
		process(v);
		res = min(res, min(dp[u][0] + dp[v][1], dp[u][1] + dp[v][0]) + d[v] - d[u]);
		dp[u][0] = min(dp[u][0], dp[v][0] + d[v] - d[u]);
		dp[u][1] = min(dp[u][1], dp[v][1] + d[v] - d[u]);
	}
}
long long Query(int S, int X[], int T, int Y[]) {
	cur++;
	sz = 0;
	for (int i = 0; i < S; i++) {
		X[i]++;
		mark[X[i]] = cur;
		col[X[i]] = 1;
		x[sz++] = X[i];
	}
	for (int i = 0; i < T; i++) {
		Y[i]++;
		mark[Y[i]] = cur;
		col[Y[i]] = 2;
		x[sz++] = Y[i];
	}
	sort(x, x + sz, [&](int u, int v) { return num[u] < num[v]; });
	for (int i = 0; i < sz - 1; i++) {
		int u = lck(x[i], x[i + 1]);
		if (mark[u] != cur) {
			mark[u] = cur;
			x[sz++] = u;
		}
	}
	sort(x, x + sz, [&](int u, int v) { return num[u] < num[v]; });
	for (int i = 0; i < sz; i++) adj2[x[i]].clear(), dp[x[i]][0] = dp[x[i]][1] = inf;
	stack<int> s;
	s.push(x[0]);
	for (int i = 1; i < sz; i++) {
		while (tail[s.top()] < num[x[i]]) s.pop();
		adj2[s.top()].push_back(x[i]);
		s.push(x[i]);
	}
	res = inf;
	process(x[0]);
	for (int i = 0; i < S; i++) col[X[i]] = 0;
	for (int i = 0; i < T; i++) col[Y[i]] = 0;
	return res;
}

// #define MAX_N 500000
// #define MAX_Q 100000
// #define MAX_SUM_ST 1000000
// #define MAX_VALUE 1000000000

// static int _N, Q;
// static int A[MAX_N], B[MAX_N], D[MAX_N];
// static int S[MAX_N];
// static int T[MAX_N];
// static int X[MAX_SUM_ST];
// static int Y[MAX_SUM_ST];

// static int Qx[MAX_N];
// static int Qy[MAX_N];

// int main() {
// 	ios::sync_with_stdio(0);
// 	cin.tie(0);

// 	int i, j, k;
// 	int STop, TTop;

// 	scanf("%d%d", &_N, &Q);
// 	for (i = 0; i < _N - 1; ++i) {
// 		scanf("%d", &A[i]);
// 		scanf("%d", &B[i]);
// 		scanf("%d", &D[i]);
// 	}

// 	STop = 0;
// 	TTop = 0;

// 	for (j = 0; j < Q; ++j) {
// 		scanf("%d%d", &S[j], &T[j]);
// 		for (k = 0; k < S[j]; ++k, ++STop) {
// 			scanf("%d", &X[STop]);
// 		}
// 		for (k = 0; k < T[j]; ++k, ++TTop) {
// 			scanf("%d", &Y[TTop]);
// 		}
// 	}

// 	STop = 0;
// 	TTop = 0;
// 	Init(_N, A, B, D);

// 	for (j = 0; j < Q; ++j) {
// 		for (k = 0; k < S[j]; k++) {
// 			Qx[k] = X[STop++];
// 		}
// 		for (k = 0; k < T[j]; k++) {
// 			Qy[k] = Y[TTop++];
// 		}

// 		printf("%lld\n", Query(S[j], Qx, T[j], Qy));
// 	}
// }

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