oj.uz

Submission #793835

# Submission time Handle Problem Language Result Execution time Memory
793835 2023-07-26T07:08:31 Z acatmeowmeow Factories (JOI14_factories) C++11
33 / 100
 8000 ms 201380 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], lift[NMAX + 5][KMAX + 5], d[NMAX + 5], h[NMAX + 5], root[NMAX + 5], rootCentroid, ans[NMAX + 5], cnt[NMAX + 5], cur = 0;
bool vis[NMAX + 5];
vector<pair<int, int>> adj[NMAX + 5];

void dfs(int u, int e) {
	lift[u][0] = e;
	for (int i = 1; i < KMAX; i++) {
		if (lift[u][i - 1] == -1) continue;
		lift[u][i] = lift[lift[u][i - 1]][i - 1];
	}
	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);	
	}
}

bool set_bit(int mask, int k) { return mask & (1ll << k); }

int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	int diff = h[v] - h[u];
	for (int i = KMAX - 1; i >= 0; i--) {
		if (!set_bit(diff, i)) continue;
		v = lift[v][i];
	}
	if (u == v) return u;
	for (int i = KMAX - 1; i >= 0; i--) {
		if (lift[u][i] != lift[v][i]) {
			u = lift[u][i], v = lift[v][i];
		}
	}
	return lift[u][0];
}

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);
	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 19 ms 12536 KB Output is correct
2 Correct 682 ms 21552 KB Output is correct
3 Correct 1352 ms 21608 KB Output is correct
4 Correct 1322 ms 21620 KB Output is correct
5 Correct 1306 ms 21892 KB Output is correct
6 Correct 195 ms 21616 KB Output is correct
7 Correct 1287 ms 21616 KB Output is correct
8 Correct 1100 ms 21856 KB Output is correct
9 Correct 1283 ms 22008 KB Output is correct
10 Correct 193 ms 21584 KB Output is correct
11 Correct 1297 ms 21728 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 2079 ms 172272 KB Output is correct
3 Correct 4841 ms 175288 KB Output is correct
4 Correct 733 ms 170004 KB Output is correct
5 Correct 6603 ms 199940 KB Output is correct
6 Correct 5022 ms 195296 KB Output is correct
7 Correct 3381 ms 66568 KB Output is correct
8 Correct 409 ms 66684 KB Output is correct
9 Correct 3780 ms 70700 KB Output is correct
10 Correct 3170 ms 68004 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12536 KB Output is correct
2 Correct 682 ms 21552 KB Output is correct
3 Correct 1352 ms 21608 KB Output is correct
4 Correct 1322 ms 21620 KB Output is correct
5 Correct 1306 ms 21892 KB Output is correct
6 Correct 195 ms 21616 KB Output is correct
7 Correct 1287 ms 21616 KB Output is correct
8 Correct 1100 ms 21856 KB Output is correct
9 Correct 1283 ms 22008 KB Output is correct
10 Correct 193 ms 21584 KB Output is correct
11 Correct 1297 ms 21728 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2079 ms 172272 KB Output is correct
14 Correct 4841 ms 175288 KB Output is correct
15 Correct 733 ms 170004 KB Output is correct
16 Correct 6603 ms 199940 KB Output is correct
17 Correct 5022 ms 195296 KB Output is correct
18 Correct 3381 ms 66568 KB Output is correct
19 Correct 409 ms 66684 KB Output is correct
20 Correct 3780 ms 70700 KB Output is correct
21 Correct 3170 ms 68004 KB Output is correct
22 Correct 3614 ms 198096 KB Output is correct
23 Correct 3360 ms 200828 KB Output is correct
24 Execution timed out 8108 ms 201380 KB Time limit exceeded
25 Halted 0 ms 0 KB -