oj.uz

Submission #156529

# Submission time Handle Problem Language Result Execution time Memory
156529 2019-10-06T10:51:37 Z Saboon Factories (JOI14_factories) C++14
100 / 100
 6062 ms 183556 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;

int st[maxn], LOG[2 * maxn], a[2 * maxn], sz[maxn], cpar[maxn], h[maxn], RMQ[22][2 * maxn];
int cnt = 0;
ll dis[maxn], dp[maxn];
bool mark[maxn];
vector<pair<int, int> > t[maxn];

int lca(int v, int u){
	if (v == u)
		return v;
	if (st[v] > st[u])
		swap(v, u);
	int len = st[u] - st[v] + 1;
	int lg = LOG[len];
	int me = RMQ[lg][st[v]], oth = RMQ[lg][st[v] + (len - (1 << lg))];
	if (h[me] < h[oth])
		return me;
	return oth;
}

ll distance(int v, int u){
	return dis[v] + dis[u] - 2ll * dis[lca(v, u)];
}

int dfs_sz(int v, int p = -1){
	sz[v] = 1;
	for (auto edge : t[v]){
		int u = edge.first;
		if (u != p and mark[u] == false)
			sz[v] += dfs_sz(u, v);
	}
	return sz[v];
}

void centroid_decomposition(int v, int centpar = -1){
	int Max = dfs_sz(v), parent = -1;
	while (true){
		bool found = 0;
		for (auto edge : t[v]){
			int u = edge.first;
			if (u != parent and mark[u] == false and sz[u] > Max / 2){
				parent = v;
				v = u;
				found = 1;
				break;
			}
		}
		if (!found)
			break;
	}
	cpar[v] = centpar;
	mark[v] = true;
	for (auto u : t[v])
		if (mark[u.first] == false)
			centroid_decomposition(u.first, v);
}

void dfs(int v, int par = -1){
	st[v] = cnt;
	a[cnt ++] = v;
	for (auto edge : t[v]){
		int u = edge.first, w = edge.second;
		if (u != par){
			h[u] = h[v] + 1;
			dis[u] = dis[v] + w;
			dfs(u, v);
			a[cnt ++] = v;
		}
	}
}

void Init(int N, int A[], int B[], int D[]){
	for (int i = 0; i < N - 1; i++){
		int v = A[i], u = B[i], w = D[i];
		t[v].push_back({u, w});
		t[u].push_back({v, w});
	}
	dfs(0);
	for (int i = 0; i < cnt; i++)
		RMQ[0][i] = a[i];
	for (int i = 1; i <= 20; i++){
		for (int j = 0; j + (1 << i) <= cnt; j++){
			int me = RMQ[i - 1][j], oth = RMQ[i - 1][j + (1 << (i-1))];
			if (h[me] <= h[oth])
				RMQ[i][j] = me;
			else
				RMQ[i][j] = oth;
		}
	}
	LOG[1] = 0;
	for (int i = 2; i <= cnt; i++)
		LOG[i] = LOG[i / 2] + 1;
	centroid_decomposition(0);
	memset(dp, 63, sizeof dp);
}

long long Query(int S, int X[], int T, int Y[]){
	for (int i = 0; i < S; i++){
		int v = X[i];
		while (v != -1){
			dp[v] = min(dp[v], distance(v, X[i]));
			v = cpar[v];
		}
	}
	ll answer = 1e18;
	for (int i = 0; i < T; i++){
		int v = Y[i];
		while (v != -1){
			answer = min(answer, dp[v] + distance(v, Y[i]));
			v = cpar[v];
		}
	}
	for (int i = 0; i < S; i++){
		int v = X[i];
		while (v != -1){
			dp[v] = 1e18;
			v = cpar[v];
		}
	}
	return answer;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16504 KB Output is correct
2 Correct 515 ms 25376 KB Output is correct
3 Correct 631 ms 25308 KB Output is correct
4 Correct 620 ms 25252 KB Output is correct
5 Correct 731 ms 25412 KB Output is correct
6 Correct 327 ms 25200 KB Output is correct
7 Correct 648 ms 25148 KB Output is correct
8 Correct 634 ms 25336 KB Output is correct
9 Correct 703 ms 25336 KB Output is correct
10 Correct 322 ms 25164 KB Output is correct
11 Correct 625 ms 25212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16248 KB Output is correct
2 Correct 2441 ms 142004 KB Output is correct
3 Correct 3403 ms 142480 KB Output is correct
4 Correct 948 ms 160912 KB Output is correct
5 Correct 4507 ms 177852 KB Output is correct
6 Correct 3461 ms 162708 KB Output is correct
7 Correct 1804 ms 61620 KB Output is correct
8 Correct 506 ms 62652 KB Output is correct
9 Correct 1858 ms 64812 KB Output is correct
10 Correct 1721 ms 63236 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16504 KB Output is correct
2 Correct 515 ms 25376 KB Output is correct
3 Correct 631 ms 25308 KB Output is correct
4 Correct 620 ms 25252 KB Output is correct
5 Correct 731 ms 25412 KB Output is correct
6 Correct 327 ms 25200 KB Output is correct
7 Correct 648 ms 25148 KB Output is correct
8 Correct 634 ms 25336 KB Output is correct
9 Correct 703 ms 25336 KB Output is correct
10 Correct 322 ms 25164 KB Output is correct
11 Correct 625 ms 25212 KB Output is correct
12 Correct 17 ms 16248 KB Output is correct
13 Correct 2441 ms 142004 KB Output is correct
14 Correct 3403 ms 142480 KB Output is correct
15 Correct 948 ms 160912 KB Output is correct
16 Correct 4507 ms 177852 KB Output is correct
17 Correct 3461 ms 162708 KB Output is correct
18 Correct 1804 ms 61620 KB Output is correct
19 Correct 506 ms 62652 KB Output is correct
20 Correct 1858 ms 64812 KB Output is correct
21 Correct 1721 ms 63236 KB Output is correct
22 Correct 3264 ms 167704 KB Output is correct
23 Correct 3707 ms 170264 KB Output is correct
24 Correct 4725 ms 168884 KB Output is correct
25 Correct 5380 ms 172668 KB Output is correct
26 Correct 5437 ms 168804 KB Output is correct
27 Correct 6062 ms 183556 KB Output is correct
28 Correct 1062 ms 171248 KB Output is correct
29 Correct 5004 ms 168668 KB Output is correct
30 Correct 5423 ms 168448 KB Output is correct
31 Correct 5711 ms 168932 KB Output is correct
32 Correct 2410 ms 65384 KB Output is correct
33 Correct 515 ms 63052 KB Output is correct
34 Correct 1416 ms 59636 KB Output is correct
35 Correct 1446 ms 59768 KB Output is correct
36 Correct 1819 ms 60040 KB Output is correct
37 Correct 1832 ms 60184 KB Output is correct