oj.uz

Submission #34313

# Submission time Handle Problem Language Result Execution time Memory
34313 2017-11-09T14:00:50 Z aome Factories (JOI14_factories) C++14
100 / 100
 4586 ms 277440 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

const int N = 500005;
const long long INF = 1e18;

typedef pair<int, int> ii;

int n, TIME;
int P[N], E[N * 2], H[N], LG[N * 2];
ii rmq[20][N * 2];
long long res;
long long dis[N];
long long f[2][N];
bool color[2][N];
vector<ii> G[N];

void dfs(int u, int p) {
	P[u] = ++TIME, E[TIME] = u;
	for (auto v : G[u]) {
		if (v.first == p) continue;
		dis[v.first] = dis[u] + v.second;
		H[v.first] = H[u] + 1, dfs(v.first, u);
		E[++TIME] = u;
	}
}

ii get(int l, int r) {
	int k = LG[r - l + 1];
	return min(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

int lca(int u, int v) {
	if (P[u] > P[v]) swap(u, v);
	return get(P[u], P[v]).second;
}

void Init(int n, int a[], int b[], int d[]) {
	for (int i = 2; i <= n * 2; ++i) LG[i] = LG[i >> 1] + 1;
	for (int i = 0; i < (n - 1); ++i) {
		G[a[i]].push_back(ii(b[i], d[i]));
		G[b[i]].push_back(ii(a[i], d[i]));
	}
	dfs(0, 0);
	for (int i = 1; i <= TIME; ++i) {
		rmq[0][i].first = H[E[i]];
		rmq[0][i].second = E[i];
	}
	for (int i = 1; i < 20; ++i) {
		for (int j = 1; j + (1 << i) - 1 <= TIME; ++j) {
			rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
		} 
	}
}

vector<int> nG[N];

void solve(int u) {
	for (int i = 0; i < 2; ++i) {
		if (color[i][u]) f[i][u] = min(f[i][u], dis[u]);
	}
	for (auto v : nG[u]) {
		solve(v);
		for (int i = 0; i < 2; ++i) f[i][u] = min(f[i][u], f[i][v]);
	}
	long long mn[2];
	mn[0] = mn[1] = INF;
	for (auto v : nG[u]) {
		for (int i = 0; i < 2; ++i) {
			res = min(res, f[i][v] + mn[i ^ 1] - 2 * dis[u]);
		}
		for (int i = 0; i < 2; ++i) {
			mn[i] = min(mn[i], f[i][v]);
		}
	}
	for (int i = 0; i < 2; ++i) {
		if (color[i ^ 1][u]) res = min(res, mn[i] - dis[u]);
	}
}

long long Query(int s, int x[], int t, int y[]) {
	vector<int> ver;
	for (int i = 0; i < s; ++i) ver.push_back(x[i]), color[0][x[i]] = 1;
	for (int i = 0; i < t; ++i) ver.push_back(y[i]), color[1][y[i]] = 1;
	sort(ver.begin(), ver.end(), [&](int x, int y) {
		return P[x] < P[y];
	});
	int sz = ver.size();
	for (int i = 1; i < sz; ++i) {
		ver.push_back(lca(ver[i - 1], ver[i]));
	}
	sort(ver.begin(), ver.end(), [&](int x, int y) {
		return P[x] < P[y];
	});
	ver.erase(unique(ver.begin(), ver.end()), ver.end());
	sz = ver.size();
	for (int i = 1; i < sz; ++i) {
		int p = lca(ver[i - 1], ver[i]);
		nG[p].push_back(ver[i]);
		// cout << p << ' ' << ver[i] << '\n';
	}
	for (int i = 0; i < sz; ++i) {
		f[0][ver[i]] = f[1][ver[i]] = INF;
	}
	res = INF, solve(ver[0]);
	for (int i = 0; i < sz; ++i) {
		color[0][ver[i]] = color[1][ver[i]] = 0;
		nG[ver[i]].clear();
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 228392 KB Output is correct
2 Correct 949 ms 228800 KB Output is correct
3 Correct 969 ms 228656 KB Output is correct
4 Correct 873 ms 228816 KB Output is correct
5 Correct 856 ms 228876 KB Output is correct
6 Correct 606 ms 228692 KB Output is correct
7 Correct 1022 ms 228656 KB Output is correct
8 Correct 939 ms 228788 KB Output is correct
9 Correct 993 ms 228872 KB Output is correct
10 Correct 716 ms 228692 KB Output is correct
11 Correct 1018 ms 228656 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 228392 KB Output is correct
2 Correct 1943 ms 247136 KB Output is correct
3 Correct 2143 ms 250752 KB Output is correct
4 Correct 1333 ms 248104 KB Output is correct
5 Correct 1899 ms 277440 KB Output is correct
6 Correct 2426 ms 250428 KB Output is correct
7 Correct 1816 ms 232984 KB Output is correct
8 Correct 1002 ms 232624 KB Output is correct
9 Correct 1353 ms 237112 KB Output is correct
10 Correct 1953 ms 232908 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3849 ms 254140 KB Output is correct
2 Correct 3543 ms 252952 KB Output is correct
3 Correct 3986 ms 258212 KB Output is correct
4 Correct 4149 ms 258300 KB Output is correct
5 Correct 4249 ms 252076 KB Output is correct
6 Correct 3716 ms 276404 KB Output is correct
7 Correct 2153 ms 250752 KB Output is correct
8 Correct 4459 ms 250964 KB Output is correct
9 Correct 4586 ms 250440 KB Output is correct
10 Correct 4379 ms 250912 KB Output is correct
11 Correct 2193 ms 239784 KB Output is correct
12 Correct 1256 ms 234800 KB Output is correct
13 Correct 1853 ms 233296 KB Output is correct
14 Correct 1933 ms 233224 KB Output is correct
15 Correct 2093 ms 233780 KB Output is correct
16 Correct 2426 ms 233732 KB Output is correct