oj.uz

Submission #793804

# Submission time Handle Problem Language Result Execution time Memory
793804 2023-07-26T06:54:46 Z acatmeowmeow Factories (JOI14_factories) C++11
15 / 100
 1525 ms 331244 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++) 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 28 ms 12508 KB Output is correct
2 Correct 673 ms 30996 KB Output is correct
3 Correct 1475 ms 31028 KB Output is correct
4 Correct 1414 ms 30952 KB Output is correct
5 Correct 1426 ms 31272 KB Output is correct
6 Correct 221 ms 30980 KB Output is correct
7 Correct 1421 ms 31164 KB Output is correct
8 Correct 1466 ms 31044 KB Output is correct
9 Correct 1373 ms 31292 KB Output is correct
10 Correct 252 ms 31060 KB Output is correct
11 Correct 1525 ms 31044 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12244 KB Output is correct
2 Runtime error 626 ms 331244 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12508 KB Output is correct
2 Correct 673 ms 30996 KB Output is correct
3 Correct 1475 ms 31028 KB Output is correct
4 Correct 1414 ms 30952 KB Output is correct
5 Correct 1426 ms 31272 KB Output is correct
6 Correct 221 ms 30980 KB Output is correct
7 Correct 1421 ms 31164 KB Output is correct
8 Correct 1466 ms 31044 KB Output is correct
9 Correct 1373 ms 31292 KB Output is correct
10 Correct 252 ms 31060 KB Output is correct
11 Correct 1525 ms 31044 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Runtime error 626 ms 331244 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -