oj.uz

Submission #793920

# Submission time Handle Problem Language Result Execution time Memory
793920 2023-07-26T08:06:39 Z acatmeowmeow Factories (JOI14_factories) C++11
100 / 100
 5376 ms 345464 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int NMAX = 5e5, KMAX = 20;
int par[NMAX + 5], sz[NMAX + 5], d[NMAX + 5], h[NMAX + 5], root[NMAX + 5], rootCentroid, ans[NMAX + 5], cnt[NMAX + 5], cur = 0;
int tin[NMAX + 5], euler[2*NMAX + 5], table[2*NMAX + 5][KMAX + 5], lg[2*NMAX + 5], timer = -1;
bool vis[NMAX + 5];
vector<pair<int, int>> adj[NMAX + 5];

void dfs(int u, int e) {
	tin[u] = ++timer;
	euler[timer] = u;
	for (auto&x : adj[u]) {
		int v = x.first, c = x.second;
		if (v == e) continue;
		d[v] = d[u] + c, h[v] = h[u] + 1;
	   	dfs(v, u);	
		euler[++timer] = u;
	}
}

int combine(int x, int y) { return h[x] < h[y] ? x : y; }

void buildTable(int n) {
	lg[1] = 0;
	for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
	for (int i = 0; i < n; i++) table[i][0] = euler[i];
	for (int j = 1; j < KMAX; j++) {
		for (int i = 0; i + (1ll << j) - 1 < n; i++) {
			table[i][j] = combine(table[i][j - 1], table[i + (1ll << (j - 1))][j - 1]);
		}
	}
}

int lca(int u, int v) {
	if (tin[u] > tin[v]) swap(u, v);
	int k = lg[tin[v] - tin[u] + 1];
	return combine(table[tin[u]][k], table[tin[v] - (1ll << k) + 1][k]);
}

int getDistance(int u, int v) {
	int w = lca(u, v);
	return d[u] + d[v] - 2*d[w];
}

void dfs2(int u, int e) {
	sz[u] = 1;
	for (auto&x : adj[u]) {
		int v = x.first;
		if (v == e || vis[v]) continue;
		dfs2(v, u);
		sz[u] += sz[v];
	}
}

int findCentroid(int u, int e, int S) {
	for (auto&x : adj[u]) {
		int v = x.first;
		if (v == e || vis[v] || sz[v] <= S/2) continue;
		return findCentroid(v, u, S);
	}
	return u;
}

int buildCentroid(int u) {
	dfs2(u, -1);
	int curCentroid = findCentroid(u, -1, sz[u]);	
	vis[curCentroid] = true;
	for (auto&x : adj[curCentroid]) {
		int v = x.first;
		if (vis[v]) continue;
		int nextCentroid = buildCentroid(v);
		root[nextCentroid] = curCentroid;
	}
	return curCentroid;
}

void Init(signed N, signed A[], signed B[], signed D[]) {
	for (int i = 0; i < N - 1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, -1);
	buildTable(2*N);
	rootCentroid = buildCentroid(0);
	root[rootCentroid] = -1;
}

long long Query(signed S, signed X[], signed T, signed Y[]) {
	cur++;
	for (int i = 0; i < T; i++) {
		for (int j = Y[i]; j != -1; j = root[j]) {
			if (cnt[j] != cur) ans[j] = 1e18;
			ans[j] = min(ans[j], getDistance(Y[i], j));
			cnt[j] = cur;
		}
	}
	int res = 1e18;
	for (int i = 0; i < S; i++) {
		for (int j = X[i]; j != -1; j = root[j]) {
			if (cnt[j] != cur) continue;
			res = min(res, getDistance(X[i], j) + ans[j]);	
		}
	}
	return res;
}

/*signed main() {
	signed N, Q;
	cin >> N >> Q;
	signed A[N], B[N], D[N];
	for (int i = 0; i < N - 1; i++) cin >> A[i] >> B[i] >> D[i];
	Init(N, A, B, D);
	for (int i = 0; i < Q; i++) {
		int S, T;
		cin >> S >> T;
		signed X[S], Y[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;
}*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12628 KB Output is correct
2 Correct 273 ms 22760 KB Output is correct
3 Correct 337 ms 22840 KB Output is correct
4 Correct 352 ms 22848 KB Output is correct
5 Correct 443 ms 23152 KB Output is correct
6 Correct 185 ms 22836 KB Output is correct
7 Correct 348 ms 22812 KB Output is correct
8 Correct 422 ms 22812 KB Output is correct
9 Correct 415 ms 23208 KB Output is correct
10 Correct 200 ms 22776 KB Output is correct
11 Correct 358 ms 22916 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 2041 ms 289648 KB Output is correct
3 Correct 2985 ms 293636 KB Output is correct
4 Correct 856 ms 287456 KB Output is correct
5 Correct 3664 ms 324156 KB Output is correct
6 Correct 2954 ms 294968 KB Output is correct
7 Correct 1533 ms 78476 KB Output is correct
8 Correct 443 ms 78188 KB Output is correct
9 Correct 1598 ms 83060 KB Output is correct
10 Correct 1311 ms 79704 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12628 KB Output is correct
2 Correct 273 ms 22760 KB Output is correct
3 Correct 337 ms 22840 KB Output is correct
4 Correct 352 ms 22848 KB Output is correct
5 Correct 443 ms 23152 KB Output is correct
6 Correct 185 ms 22836 KB Output is correct
7 Correct 348 ms 22812 KB Output is correct
8 Correct 422 ms 22812 KB Output is correct
9 Correct 415 ms 23208 KB Output is correct
10 Correct 200 ms 22776 KB Output is correct
11 Correct 358 ms 22916 KB Output is correct
12 Correct 7 ms 12500 KB Output is correct
13 Correct 2041 ms 289648 KB Output is correct
14 Correct 2985 ms 293636 KB Output is correct
15 Correct 856 ms 287456 KB Output is correct
16 Correct 3664 ms 324156 KB Output is correct
17 Correct 2954 ms 294968 KB Output is correct
18 Correct 1533 ms 78476 KB Output is correct
19 Correct 443 ms 78188 KB Output is correct
20 Correct 1598 ms 83060 KB Output is correct
21 Correct 1311 ms 79704 KB Output is correct
22 Correct 3154 ms 291336 KB Output is correct
23 Correct 2802 ms 293676 KB Output is correct
24 Correct 4454 ms 295372 KB Output is correct
25 Correct 4328 ms 323408 KB Output is correct
26 Correct 4171 ms 319744 KB Output is correct
27 Correct 5376 ms 345464 KB Output is correct
28 Correct 1108 ms 316048 KB Output is correct
29 Correct 4176 ms 319376 KB Output is correct
30 Correct 4507 ms 318664 KB Output is correct
31 Correct 4522 ms 319372 KB Output is correct
32 Correct 1810 ms 95976 KB Output is correct
33 Correct 473 ms 90516 KB Output is correct
34 Correct 1086 ms 87728 KB Output is correct
35 Correct 1172 ms 87728 KB Output is correct
36 Correct 1450 ms 88644 KB Output is correct
37 Correct 1224 ms 88644 KB Output is correct