oj.uz

Submission #34868

# Submission time Handle Problem Language Result Execution time Memory
34868 2017-11-16T09:58:27 Z cheater2k Factories (JOI14_factories) C++14
100 / 100
 4616 ms 277444 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;

int n;
vector< pair<int,int> > G[N];
int t[N], TIME;
int dep[N], e[N << 1], lg[N << 1];
pair<int,int> rmq[N << 1][20];
long long dist[N];

void dfs(int u, int p) {
	t[u] = ++TIME; e[TIME] = u;
	for (auto &edge : G[u]) {
		int v = edge.second, w = edge.first; if (v == p) continue;
		dist[v] = dist[u] + w; dep[v] = dep[u] + 1; dfs(v, u);
		e[++TIME] = u;
	}
}

int get(int l, int r) {
	int k = lg[r - l + 1];
	pair<int,int> res = min(rmq[l][k], rmq[r - (1 << k) + 1][k]);
	return res.second;
}

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

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < N - 1; ++i) {
		G[A[i]].push_back(make_pair(D[i], B[i]));
		G[B[i]].push_back(make_pair(D[i], A[i]));
	}
	dfs(0, 0);
	for (int i = 1; i <= TIME; ++i) rmq[i][0] = make_pair(dep[e[i]], e[i]);
	for (int j = 1; j <= 19; ++j) for (int i = 1; i <= TIME; ++i) {
		rmq[i][j] = min(rmq[i][j-1], rmq[i + (1 << j-1)][j-1]);
	}
	for (int i = 2; i <= TIME; ++i) lg[i] = lg[i >> 1] + 1;
}

// ------------------------------------------------------------------

const long long inf = 1e18;
vector<int> nG[N];
long long f[N][2];
bool a[N][2];
long long ans;

void solve(int u) {
	for (int i = 0; i < 2; ++i) if (a[u][i]) f[u][i] = 0;
	for (int v : nG[u]) {
		solve(v);
		for (int i = 0; i < 2; ++i) f[u][i] = min(f[u][i], f[v][i] + dist[v] - dist[u]);
	}
	ans = min(ans, f[u][0] + f[u][1]);
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<int> imp;

	// build a new tree containing at most 2 * (S + T) vertices
	for (int i = 0; i < S; ++i) a[X[i]][0] = 1, imp.push_back(X[i]);
	for (int i = 0; i < T; ++i) a[Y[i]][1] = 1, imp.push_back(Y[i]);
	sort(imp.begin(), imp.end(), [&](int x, int y) { return t[x] < t[y]; });
	
	int sz = imp.size();
	for (int i = 1; i < sz; ++i) {
		imp.push_back(lca(imp[i-1], imp[i]));
	}
	sort(imp.begin(), imp.end(), [&](int x, int y) { return t[x] < t[y]; });
	imp.resize(distance(imp.begin(), unique(imp.begin(), imp.end())));

	sz = imp.size();
	for (int i = 1; i < sz; ++i) {
		int p = lca(imp[i-1], imp[i]);
		nG[p].push_back(imp[i]);
	}

	// solve
	ans = inf;
	for (int u : imp) f[u][0] = f[u][1] = inf;
	solve(imp[0]);

	// reset
	for (int i = 0; i < S; ++i) a[X[i]][0] = 0;
	for (int i = 0; i < T; ++i) a[Y[i]][1] = 0;
	for (int u : imp) nG[u].clear();

	return ans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:43:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   rmq[i][j] = min(rmq[i][j-1], rmq[i + (1 << j-1)][j-1]);
                                               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 228392 KB Output is correct
2 Correct 953 ms 228800 KB Output is correct
3 Correct 1018 ms 228656 KB Output is correct
4 Correct 913 ms 228816 KB Output is correct
5 Correct 953 ms 228872 KB Output is correct
6 Correct 603 ms 228692 KB Output is correct
7 Correct 953 ms 228656 KB Output is correct
8 Correct 949 ms 228788 KB Output is correct
9 Correct 893 ms 228876 KB Output is correct
10 Correct 579 ms 228692 KB Output is correct
11 Correct 903 ms 228656 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 228392 KB Output is correct
2 Correct 2366 ms 247136 KB Output is correct
3 Correct 2783 ms 250752 KB Output is correct
4 Correct 1899 ms 248104 KB Output is correct
5 Correct 2439 ms 277444 KB Output is correct
6 Correct 2816 ms 250428 KB Output is correct
7 Correct 1829 ms 232980 KB Output is correct
8 Correct 1259 ms 232624 KB Output is correct
9 Correct 1663 ms 237116 KB Output is correct
10 Correct 2049 ms 232912 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 4283 ms 254140 KB Output is correct
2 Correct 3836 ms 252952 KB Output is correct
3 Correct 4596 ms 258212 KB Output is correct
4 Correct 4453 ms 258296 KB Output is correct
5 Correct 4616 ms 252080 KB Output is correct
6 Correct 4356 ms 276400 KB Output is correct
7 Correct 2823 ms 250752 KB Output is correct
8 Correct 4349 ms 250960 KB Output is correct
9 Correct 4476 ms 250436 KB Output is correct
10 Correct 4593 ms 250912 KB Output is correct
11 Correct 2146 ms 239440 KB Output is correct
12 Correct 1669 ms 234800 KB Output is correct
13 Correct 2133 ms 233296 KB Output is correct
14 Correct 2013 ms 233224 KB Output is correct
15 Correct 2229 ms 233776 KB Output is correct
16 Correct 2356 ms 233728 KB Output is correct