oj.uz

Submission #793910

# Submission time Handle Problem Language Result Execution time Memory
793910 2023-07-26T07:59:58 Z acatmeowmeow Factories (JOI14_factories) C++11
15 / 100
 1369 ms 524288 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], table[2*NMAX + 5][KMAX + 5], lg[NMAX + 5];
bool vis[NMAX + 5];
vector<pair<int, int>> adj[NMAX + 5];
vector<int> euler;

void dfs(int u, int e) {
	euler.push_back(u);
	tin[u] = euler.size() - 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);	
		euler.push_back(u);
	}
}

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

void buildTable() {
	int n = euler.size();
	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();
	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 10 ms 12628 KB Output is correct
2 Correct 301 ms 22852 KB Output is correct
3 Correct 366 ms 22940 KB Output is correct
4 Correct 344 ms 22944 KB Output is correct
5 Correct 406 ms 23256 KB Output is correct
6 Correct 164 ms 22864 KB Output is correct
7 Correct 344 ms 22960 KB Output is correct
8 Correct 336 ms 22904 KB Output is correct
9 Correct 411 ms 23280 KB Output is correct
10 Correct 177 ms 22872 KB Output is correct
11 Correct 331 ms 22944 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12500 KB Output is correct
2 Runtime error 1369 ms 524288 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 10 ms 12628 KB Output is correct
2 Correct 301 ms 22852 KB Output is correct
3 Correct 366 ms 22940 KB Output is correct
4 Correct 344 ms 22944 KB Output is correct
5 Correct 406 ms 23256 KB Output is correct
6 Correct 164 ms 22864 KB Output is correct
7 Correct 344 ms 22960 KB Output is correct
8 Correct 336 ms 22904 KB Output is correct
9 Correct 411 ms 23280 KB Output is correct
10 Correct 177 ms 22872 KB Output is correct
11 Correct 331 ms 22944 KB Output is correct
12 Correct 8 ms 12500 KB Output is correct
13 Runtime error 1369 ms 524288 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -