oj.uz

Submission #787301

# Submission time Handle Problem Language Result Execution time Memory
787301 2023-07-19T04:16:31 Z marvinthang Factories (JOI14_factories) C++17
100 / 100
 1844 ms 183904 KB 
/*************************************
*    author: marvinthang             *
*    created: 19.07.2023 10:57:43    *
*************************************/

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

const long long INF = 1e18;
const int MAX = 5e5 + 5;
const int LOG = 20;

int N;
vector <pair <int, int>> adj[MAX];
int depth[MAX], nodes[MAX + MAX][LOG], nodeCount, tin[MAX], tout[MAX];
long long length[MAX];

void dfs(int u, int par) {
	nodes[++nodeCount][0] = u;
	tin[u] = nodeCount;
	for (auto [w, v]: adj[u]) if (v != par) {
		length[v] = length[u] + w;
		depth[v] = depth[u] + 1;
		dfs(v, u);
		nodes[++nodeCount][0] = u;
	}
	tout[u] = nodeCount;
}

#define MIN_DEPTH(a, b) (depth[(a)] < depth[(b)] ? a : b)

void Init(int n, int A[], int B[], int D[]) {
	N = n;
	REP(i, N - 1) {
		adj[A[i]].emplace_back(D[i], B[i]);
		adj[B[i]].emplace_back(D[i], A[i]);
	}
	dfs(0, 0);
	for (int k = 1; MASK(k) <= nodeCount; ++k) 
		FORE(i, 1, nodeCount - MASK(k) + 1) nodes[i][k] = MIN_DEPTH(nodes[i][k - 1], nodes[i + MASK(k - 1)][k - 1]);
}

int get_lca(int u, int v) {
	u = tin[u]; v = tin[v];
	if (u > v) swap(u, v);
	int h = __lg(v - u + 1);
	return MIN_DEPTH(nodes[u][h], nodes[v - MASK(h) + 1][h]);
}

bool isChild(int u, int v) {
	return tin[u] <= tin[v] && tin[v] <= tout[u];
}

vector <pair <long long, int>> tadj[MAX];
int type[MAX];

long long Query(int S, int X[], int T, int Y[]) {
	vector <int> vertices;
	REP(i, S) {
		vertices.push_back(X[i]);
		type[X[i]] = 1;
	}
	REP(i, T) {
		vertices.push_back(Y[i]);
		type[Y[i]] = 2;
	}
	sort(ALL(vertices), [&] (int a, int b) { return tin[a] < tin[b]; });
	REP(i, (int) vertices.size() - 1) vertices.push_back(get_lca(vertices[i], vertices[i + 1]));
	sort(ALL(vertices), [&] (int a, int b) { return tin[a] < tin[b]; });
	vertices.erase(unique(ALL(vertices)), vertices.end());

	stack <int> st;
	for (int u: vertices) {
		if (!st.empty()) {
			while (!isChild(st.top(), u)) st.pop();
			tadj[st.top()].emplace_back(length[u] - length[st.top()], u);
		}
		st.push(u);
	}
	long long res = INF;

	function <array<long long, 2>(int, int)> dfs = [&] (int u, int par) {
		array <long long, 2> cur = {INF, INF};
		if (type[u]) cur[type[u] - 1] = 0;
		for (auto [w, v]: tadj[u]) if (v != par) {
			array <long long, 2> f = dfs(v, u);
			REP(i, 2) cur[i] = min(cur[i], f[i] + w);
		}
		res = min(res, cur[0] + cur[1]);
		return cur;
	};
	dfs(vertices[0], 0);
	for (int u: vertices) {
		tadj[u].clear();
		type[u] = 0;
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24220 KB Output is correct
2 Correct 545 ms 33132 KB Output is correct
3 Correct 516 ms 33064 KB Output is correct
4 Correct 551 ms 33196 KB Output is correct
5 Correct 587 ms 33436 KB Output is correct
6 Correct 369 ms 33100 KB Output is correct
7 Correct 513 ms 33096 KB Output is correct
8 Correct 535 ms 33356 KB Output is correct
9 Correct 489 ms 33424 KB Output is correct
10 Correct 335 ms 33136 KB Output is correct
11 Correct 517 ms 33096 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24056 KB Output is correct
2 Correct 910 ms 145348 KB Output is correct
3 Correct 1016 ms 148852 KB Output is correct
4 Correct 680 ms 145964 KB Output is correct
5 Correct 1000 ms 182024 KB Output is correct
6 Correct 1094 ms 150184 KB Output is correct
7 Correct 631 ms 57144 KB Output is correct
8 Correct 483 ms 57132 KB Output is correct
9 Correct 577 ms 63060 KB Output is correct
10 Correct 651 ms 58416 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24220 KB Output is correct
2 Correct 545 ms 33132 KB Output is correct
3 Correct 516 ms 33064 KB Output is correct
4 Correct 551 ms 33196 KB Output is correct
5 Correct 587 ms 33436 KB Output is correct
6 Correct 369 ms 33100 KB Output is correct
7 Correct 513 ms 33096 KB Output is correct
8 Correct 535 ms 33356 KB Output is correct
9 Correct 489 ms 33424 KB Output is correct
10 Correct 335 ms 33136 KB Output is correct
11 Correct 517 ms 33096 KB Output is correct
12 Correct 12 ms 24056 KB Output is correct
13 Correct 910 ms 145348 KB Output is correct
14 Correct 1016 ms 148852 KB Output is correct
15 Correct 680 ms 145964 KB Output is correct
16 Correct 1000 ms 182024 KB Output is correct
17 Correct 1094 ms 150184 KB Output is correct
18 Correct 631 ms 57144 KB Output is correct
19 Correct 483 ms 57132 KB Output is correct
20 Correct 577 ms 63060 KB Output is correct
21 Correct 651 ms 58416 KB Output is correct
22 Correct 1763 ms 156156 KB Output is correct
23 Correct 1519 ms 156992 KB Output is correct
24 Correct 1822 ms 160672 KB Output is correct
25 Correct 1844 ms 163588 KB Output is correct
26 Correct 1560 ms 153320 KB Output is correct
27 Correct 1841 ms 183904 KB Output is correct
28 Correct 1079 ms 154820 KB Output is correct
29 Correct 1526 ms 151812 KB Output is correct
30 Correct 1494 ms 151340 KB Output is correct
31 Correct 1522 ms 151728 KB Output is correct
32 Correct 848 ms 67724 KB Output is correct
33 Correct 574 ms 59948 KB Output is correct
34 Correct 794 ms 56324 KB Output is correct
35 Correct 790 ms 56164 KB Output is correct
36 Correct 761 ms 57076 KB Output is correct
37 Correct 762 ms 56964 KB Output is correct