oj.uz

Submission #39500

# Submission time Handle Problem Language Result Execution time Memory
39500 2018-01-16T03:23:09 Z 14kg Factories (JOI14_factories) C++11
15 / 100
 6000 ms 128872 KB 
#include "factories.h"
#include <algorithm>
#include <vector>
#define N 500001
#define NN 1048576
#define LL long long
#define INF 999999999999999999
#define max2(x,y) (x>y?x:y)

using namespace std;
int n, nn, t[N], tree_up[N][20], p[20];
int tree_lev[N], tree_e[N];
LL deep[N], seg[2][NN];
vector<pair<int, int> > r[N];

int dfs_lev, q_len, q[N*3];

LL min2(LL x, LL y) {
	return x < y ? x : y;
}
void dfs(int x, int up, LL _deep, int _t) {
	tree_lev[x] = ++dfs_lev;
	deep[dfs_lev] = _deep, t[dfs_lev] = _t;

	tree_up[dfs_lev][0] = tree_lev[up];
	for (int i = 1; i < 20; i++) 
		tree_up[dfs_lev][i] = tree_up[tree_up[dfs_lev][i - 1]][i - 1];

	for (auto i : r[x])
		if (i.first != up) dfs(i.first, x, _deep + (LL)i.second, _t + 1);
	tree_e[tree_lev[x]] = dfs_lev;
}
void Init(int _n, int *a, int *b, int *d) {
	n = _n;
	for (nn = 1; nn < n; nn *= 2);
	for (int i = 1; i < nn * 2; i++) seg[0][i] = seg[1][i] = INF;

	for (int i = 0; i < n - 1; i++) {
		r[a[i] + 1].push_back({ b[i] + 1,d[i] });
		r[b[i] + 1].push_back({ a[i] + 1,d[i] });
	} dfs(1, 0, 0, 1);
	
	p[0] = 1;
	for (int i = 1; i < 20; i++) p[i] = p[i - 1] * 2;
}

int lca(int x, int y) {
	for (int i = 19; i >= 0; i--)
		if (t[x] - p[i] >= t[y]) x = tree_up[x][i];
	for (int i = 19; i >= 0; i--)
		if (t[y] - p[i] >= t[x]) y = tree_up[y][i];
	for(int i=19; i>=0; i--)
		if (tree_up[x][i] != tree_up[y][i]) 
			x = tree_up[x][i], y = tree_up[y][i];

	if (x != y) x = tree_up[x][0];
	return x;
}
void Update(int x, int y) {
	seg[x][y] = min2(seg[x][y * 2], seg[x][y * 2 + 1]);
	if (y > 1) Update(x, y / 2);
}
LL get_seg(int lev, int l, int r, int x, int y, int seg_num) {
	int mid = (l + r) / 2;

	if (r < x || y < l) return INF;
	if (x <= l && r <= y) return seg[seg_num][lev];
	return min2(get_seg(lev * 2, l, mid, x, y, seg_num), get_seg(lev * 2 + 1, mid + 1, r, x, y, seg_num));
}
LL Query(int a_len, int a[], int b_len, int b[]) {
	int temp;
	LL out = INF, len1, len2, len3;
	
	q_len = 0;
	for (int i = 0; i < a_len; i++) {
		temp = tree_lev[a[i] + 1];
		q[++q_len] = temp, seg[0][nn + temp - 1] = deep[temp];
		Update(0, (nn + temp - 1) / 2);
	}
	for (int i = 0; i < b_len; i++) {
		temp = tree_lev[b[i] + 1];
		q[++q_len] = temp, seg[1][nn + temp - 1] = deep[temp];
		Update(1, (nn + temp - 1) / 2);
	}
	
	for (int i = 1; i <= q_len; i++) {
		len1 = len2 = deep[q[i]];
		if (i > a_len) len1 = get_seg(1, 1, nn, q[i], tree_e[q[i]], 0);
		else len2 = get_seg(1, 1, nn, q[i], tree_e[q[i]], 1);
		len3 = deep[q[i]];
		
		out = min2(out, len1 + len2 - len3 * 2);
	}
	sort(q + 1, q + q_len + 1);
	for (int i = 1; i < q_len; i++) {
		temp = lca(q[i], q[i + 1]);
		len1 = get_seg(1, 1, nn, temp, tree_e[temp], 0);
		len2 = get_seg(1, 1, nn, temp, tree_e[temp], 1);
		len3 = deep[temp];

		out = min2(out, len1 + len2 - len3 * 2);
	}
	
	for (int i = 0; i < a_len; i++) {
		temp = tree_lev[a[i] + 1];
		seg[0][nn + temp - 1] = INF;
		Update(0, (nn + temp - 1) / 2);
	}
	for (int i = 0; i < b_len; i++) {
		temp = tree_lev[b[i] + 1];
		seg[1][nn + temp - 1] = INF;
		Update(1, (nn + temp - 1) / 2);
	}
	return out;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 106232 KB Output is correct
2 Correct 2226 ms 106496 KB Output is correct
3 Correct 2689 ms 106496 KB Output is correct
4 Correct 2509 ms 106496 KB Output is correct
5 Correct 2456 ms 106584 KB Output is correct
6 Correct 2169 ms 106532 KB Output is correct
7 Correct 3073 ms 106496 KB Output is correct
8 Correct 2773 ms 106496 KB Output is correct
9 Correct 2653 ms 106588 KB Output is correct
10 Correct 2163 ms 106532 KB Output is correct
11 Correct 2849 ms 106496 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 106232 KB Output is correct
2 Correct 4349 ms 124976 KB Output is correct
3 Execution timed out 6000 ms 128872 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6000 ms 124976 KB Execution timed out
2 Halted 0 ms 0 KB -