oj.uz

Submission #255757

# Submission time Handle Problem Language Result Execution time Memory
255757 2020-08-01T19:37:47 Z islingr Factories (JOI14_factories) C++17
100 / 100
 7913 ms 150712 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a); )
#define sz(x...) int((x).size())
#define all(x) begin(x), end(x)
#define eb(x...) emplace_back(x)
#define lb(x...) lower_bound(x)

template<class T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

using ll = int64_t;

const ll inf = 1e18;
const int B = 19, N = 1 << B;
int dep[N], p[N][B], in[N];
ll dist[N];

void Init(int n, int a[], int b[], int d[]) {
	vector<vector<int>> g(n);
	rep(e, 0, n - 1) g[a[e]].eb(e), g[b[e]].eb(e);
	int timer = 0;
	function<void(int)> dfs = [&](int u) {
		in[u] = timer++;
		for (int e : g[u]) {
			int v = u != a[e] ? a[e] : b[e];
			if (v == p[u][0]) continue;
			dist[v] = dist[u] + d[e];
			dep[v] = dep[u] + 1;
			p[v][0] = u;
			rep(j, 0, B - 1) p[v][j + 1] = p[p[v][j]][j];
			dfs(v);
		}
	};
	dfs(0);
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	per(j, 0, B) if (dep[v] <= dep[p[u][j]]) u = p[u][j];
	if (u == v) return u;
	per(j, 0, B) if (p[u][j] != p[v][j]) u = p[u][j], v = p[v][j];
	return p[u][0];
}

vector<int> g[N];
short col[N];
ll s[N], t[N];

ll Query(int S, int X[], int T, int Y[]) {
	vector<int> V; V.reserve(S + T);
	rep(i, 0, S) col[X[i]] = +1, V.eb(X[i]);
	rep(i, 0, T) col[Y[i]] = -1, V.eb(Y[i]);
	sort(all(V), [&](int x, int y) { return in[x] < in[y]; });
	rep(i, 1, S + T) V.eb(lca(V[i - 1], V[i]));
	sort(all(V), [&](int x, int y) { return in[x] < in[y]; });
	V.erase(unique(all(V)), end(V));
	rep(i, 1, sz(V)) g[lca(V[i - 1], V[i])].eb(V[i]);
	ll ans = inf;
	function<void(int)> dfs = [&](int u) {
		s[u] = t[u] = inf;
		if (col[u] > 0) s[u] = 0;
		if (col[u] < 0) t[u] = 0;
		for (int v : g[u]) {
			dfs(v);
			ckmin(s[u], dist[v] - dist[u] + s[v]);
			ckmin(t[u], dist[v] - dist[u] + t[v]);
		}
		ckmin(ans, s[u] + t[u]);
	};
	dfs(V[0]);
	for (int v : V) g[v].clear(), col[v] = 0;
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 13304 KB Output is correct
2 Correct 1611 ms 30940 KB Output is correct
3 Correct 1768 ms 30980 KB Output is correct
4 Correct 1656 ms 31076 KB Output is correct
5 Correct 1414 ms 31464 KB Output is correct
6 Correct 1296 ms 31056 KB Output is correct
7 Correct 1750 ms 31032 KB Output is correct
8 Correct 1656 ms 31112 KB Output is correct
9 Correct 1347 ms 31284 KB Output is correct
10 Correct 1254 ms 31092 KB Output is correct
11 Correct 1741 ms 30968 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12928 KB Output is correct
2 Correct 2356 ms 115320 KB Output is correct
3 Correct 4450 ms 118136 KB Output is correct
4 Correct 1445 ms 116424 KB Output is correct
5 Correct 3117 ms 148608 KB Output is correct
6 Correct 4728 ms 118968 KB Output is correct
7 Correct 3667 ms 51744 KB Output is correct
8 Correct 1631 ms 52036 KB Output is correct
9 Correct 2823 ms 56748 KB Output is correct
10 Correct 3540 ms 53088 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 13304 KB Output is correct
2 Correct 1611 ms 30940 KB Output is correct
3 Correct 1768 ms 30980 KB Output is correct
4 Correct 1656 ms 31076 KB Output is correct
5 Correct 1414 ms 31464 KB Output is correct
6 Correct 1296 ms 31056 KB Output is correct
7 Correct 1750 ms 31032 KB Output is correct
8 Correct 1656 ms 31112 KB Output is correct
9 Correct 1347 ms 31284 KB Output is correct
10 Correct 1254 ms 31092 KB Output is correct
11 Correct 1741 ms 30968 KB Output is correct
12 Correct 11 ms 12928 KB Output is correct
13 Correct 2356 ms 115320 KB Output is correct
14 Correct 4450 ms 118136 KB Output is correct
15 Correct 1445 ms 116424 KB Output is correct
16 Correct 3117 ms 148608 KB Output is correct
17 Correct 4728 ms 118968 KB Output is correct
18 Correct 3667 ms 51744 KB Output is correct
19 Correct 1631 ms 52036 KB Output is correct
20 Correct 2823 ms 56748 KB Output is correct
21 Correct 3540 ms 53088 KB Output is correct
22 Correct 4509 ms 123768 KB Output is correct
23 Correct 4137 ms 124860 KB Output is correct
24 Correct 5343 ms 126840 KB Output is correct
25 Correct 5385 ms 128504 KB Output is correct
26 Correct 7631 ms 127136 KB Output is correct
27 Correct 5174 ms 150712 KB Output is correct
28 Correct 2478 ms 126312 KB Output is correct
29 Correct 7742 ms 126580 KB Output is correct
30 Correct 7885 ms 126084 KB Output is correct
31 Correct 7913 ms 126708 KB Output is correct
32 Correct 2872 ms 58480 KB Output is correct
33 Correct 1660 ms 52524 KB Output is correct
34 Correct 2794 ms 49916 KB Output is correct
35 Correct 2654 ms 49912 KB Output is correct
36 Correct 3538 ms 50552 KB Output is correct
37 Correct 3747 ms 50576 KB Output is correct