Submission #39500

#	Time	Username	Problem	Language	Result	Execution time	Memory
39500		14kg	Factories (JOI14_factories)	C++11	15 / 100	6000 ms	128872 KiB

factories

#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 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67