oj.uz

Submission #793817

# Submission time Handle Problem Language Result Execution time Memory
793817 2023-07-26T07:00:58 Z acatmeowmeow Factories (JOI14_factories) C++11
15 / 100
 8000 ms 213216 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];
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[]) {
	for (int i = 0; i < T; i++) {
		for (int j = Y[i]; j != -1; j = root[j]) {
			ans[j] = 1e18;	
		}
	}
	for (int i = 0; i < S; i++) {
		for (int j = X[i]; j != -1; j = root[j]) {
			ans[j] = 1e18;
		}
	}
	for (int i = 0; i < T; i++) {
		for (int j = Y[i]; j != -1; j = root[j]) {
			ans[j] = min(ans[j], getDistance(Y[i], j));
		}
	}
	int res = 1e18;
	for (int i = 0; i < S; i++) {
		for (int j = X[i]; j != -1; j = root[j]) {
			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 20 ms 12508 KB Output is correct
2 Correct 658 ms 21464 KB Output is correct
3 Correct 1399 ms 21552 KB Output is correct
4 Correct 1357 ms 21544 KB Output is correct
5 Correct 1316 ms 21828 KB Output is correct
6 Correct 219 ms 21564 KB Output is correct
7 Correct 1396 ms 21536 KB Output is correct
8 Correct 1425 ms 21692 KB Output is correct
9 Correct 1353 ms 21936 KB Output is correct
10 Correct 226 ms 21532 KB Output is correct
11 Correct 1403 ms 21564 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 2683 ms 168408 KB Output is correct
3 Correct 6273 ms 189308 KB Output is correct
4 Correct 722 ms 184344 KB Output is correct
5 Execution timed out 8038 ms 213216 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12508 KB Output is correct
2 Correct 658 ms 21464 KB Output is correct
3 Correct 1399 ms 21552 KB Output is correct
4 Correct 1357 ms 21544 KB Output is correct
5 Correct 1316 ms 21828 KB Output is correct
6 Correct 219 ms 21564 KB Output is correct
7 Correct 1396 ms 21536 KB Output is correct
8 Correct 1425 ms 21692 KB Output is correct
9 Correct 1353 ms 21936 KB Output is correct
10 Correct 226 ms 21532 KB Output is correct
11 Correct 1403 ms 21564 KB Output is correct
12 Correct 9 ms 12244 KB Output is correct
13 Correct 2683 ms 168408 KB Output is correct
14 Correct 6273 ms 189308 KB Output is correct
15 Correct 722 ms 184344 KB Output is correct
16 Execution timed out 8038 ms 213216 KB Time limit exceeded
17 Halted 0 ms 0 KB -