oj.uz

Submission #39503

# Submission time Handle Problem Language Result Execution time Memory
39503 2018-01-16T03:48:48 Z 14kg Factories (JOI14_factories) C++11
100 / 100
 4099 ms 144720 KB 
#include "factories.h"
#include <algorithm>
#include <vector>
#define N 500001
#define LL long long
#define INF 999999999999999999
#define min2(x,y) (x<y?x:y)

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

int dfs_lev, q_len, dfs_num;
LL out;
pair<int, int> q[N * 3];

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 (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;
}
pair<LL,LL> dfs2() {
	int lev = q[dfs_num].first;
	bool type[3] = { 0 };
	LL MIN1 = INF, MIN2 = INF;

	type[q[dfs_num].second] = true, dfs_num++;
	while (q[dfs_num].first == lev) type[q[dfs_num].second] = true, dfs_num++;

	while (tree_e[lev] >= q[dfs_num].first) {
		pair<LL, LL> temp = dfs2();
		MIN1 = min2(MIN1, temp.first), MIN2 = min2(MIN2, temp.second);
	}
	if (type[1]) MIN1 = min2(MIN1, deep[lev]);
	if (type[2]) MIN2 = min2(MIN2, deep[lev]);
	out = min2(out, MIN1 + MIN2 - deep[lev] * 2);
	return { MIN1,MIN2 };
}
LL Query(int a_len, int a[], int b_len, int b[]) {
	int temp;

	q_len = 0, out = INF;
	for (int i = 0; i < a_len; i++) {
		temp = tree_lev[a[i] + 1];
		q[++q_len] = { temp,1 };
	}
	for (int i = 0; i < b_len; i++) {
		temp = tree_lev[b[i] + 1];
		q[++q_len] = { temp,2 };
	}
	sort(q + 1, q + q_len + 1), temp = q_len;
	for (int i = 1; i < temp; i++) q[++q_len] = { lca(q[i].first, q[i + 1].first),0 };
	sort(q + 1, q + q_len + 1), q[q_len + 1] = { n + 1, 0 };

	dfs_num=1, dfs2();

	return out;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 95708 KB Output is correct
2 Correct 1076 ms 95972 KB Output is correct
3 Correct 1046 ms 95972 KB Output is correct
4 Correct 1086 ms 95972 KB Output is correct
5 Correct 1093 ms 96064 KB Output is correct
6 Correct 846 ms 96008 KB Output is correct
7 Correct 1129 ms 95972 KB Output is correct
8 Correct 1073 ms 95972 KB Output is correct
9 Correct 1033 ms 96064 KB Output is correct
10 Correct 819 ms 96008 KB Output is correct
11 Correct 1149 ms 95972 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 95708 KB Output is correct
2 Correct 2119 ms 114452 KB Output is correct
3 Correct 2506 ms 118344 KB Output is correct
4 Correct 1433 ms 115420 KB Output is correct
5 Correct 3006 ms 144720 KB Output is correct
6 Correct 2343 ms 117812 KB Output is correct
7 Correct 1699 ms 100116 KB Output is correct
8 Correct 1086 ms 99940 KB Output is correct
9 Correct 2246 ms 102816 KB Output is correct
10 Correct 1779 ms 99996 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2593 ms 114452 KB Output is correct
2 Correct 2849 ms 114452 KB Output is correct
3 Correct 2433 ms 117116 KB Output is correct
4 Correct 2673 ms 117836 KB Output is correct
5 Correct 3466 ms 117660 KB Output is correct
6 Correct 3133 ms 137500 KB Output is correct
7 Correct 1766 ms 115420 KB Output is correct
8 Correct 3889 ms 117204 KB Output is correct
9 Correct 3709 ms 116540 KB Output is correct
10 Correct 4099 ms 117252 KB Output is correct
11 Correct 1646 ms 103416 KB Output is correct
12 Correct 1196 ms 99940 KB Output is correct
13 Correct 1903 ms 99404 KB Output is correct
14 Correct 1849 ms 99404 KB Output is correct
15 Correct 1816 ms 100000 KB Output is correct
16 Correct 1633 ms 99992 KB Output is correct