oj.uz

Submission #779439

# Submission time Handle Problem Language Result Execution time Memory
779439 2023-07-11T12:01:47 Z TranGiaHuy1508 Factories (JOI14_factories) C++17
100 / 100
 4582 ms 183544 KB 
#include <bits/stdc++.h>
using namespace std;

#include "factories.h"

#define distance _distance

using ll = long long;
using ii = pair<int, int>;

namespace {
	struct Edge{
		int to;
		ll d;
	};

	// Main variables
	const ll inf = 1e18;

	int n, lg, timer;
	vector<int> depth, tin, tout;
	vector<ll> distance;
	vector<vector<int>> parent;
	vector<vector<Edge>> adj;

	// Main functions
	void dfs(int x, int p = -1, int d = 0, ll dist = 0){
		depth[x] = d;
		distance[x] = dist;
		tin[x] = timer++;
		parent[0][x] = (p < 0) ? x : p;

		for (auto edge: adj[x]){
			int k = edge.to;
			if (k == p) continue;
			dfs(k, x, d + 1, dist + edge.d);
		}

		tout[x] = timer;
	}

	int LCA(int x, int y){
		if (depth[x] > depth[y]) swap(x, y);
		for (int j = lg-1; j >= 0; j--){
			if (depth[y] - (1 << j) >= depth[x]){
				y = parent[j][y];
			}
		}
		if (x == y) return x;
		for (int j = lg-1; j >= 0; j--){
			if (parent[j][x] != parent[j][y]){
				x = parent[j][x];
				y = parent[j][y];
			}
		}
		return parent[0][x];
	}

	// Query variables
	vector<int> reset_queue;
	vector<int> color;
	vector<vector<int>> graph;

	// Query functions
	vector<ll> solve(ll &res, int x, int p = -1){
		vector<ll> mindist(2, inf);
		if (color[x] >= 0) mindist[color[x]] = 0;

		for (auto k: graph[x]){
			if (k == p) continue;
			auto subdist = solve(res, k, x);
			for (int j = 0; j < 2; j++){
				mindist[j] = min(mindist[j], subdist[j] + distance[k] - distance[x]);
			}
		}

		res = min(res, mindist[0] + mindist[1]);
		return mindist;
	}
}

void Init(int N, int A[], int B[], int D[]){
	// Initialize
	n = N;
	lg = 31 - __builtin_clz(n) + 1;
	timer = 0;

	depth.resize(n);
	tin.resize(n);
	tout.resize(n);
	distance.resize(n);
	parent.assign(lg, vector<int>(n));
	adj.resize(n);
	color.assign(n, -1);
	graph.resize(n);

	for (int i = 0; i < n; i++){
		int a = A[i], b = B[i], d = D[i];
		adj[a].push_back(Edge{b, d});
		adj[b].push_back(Edge{a, d});
	}

	// DFS
	dfs(0);
	for (int j = 1; j < lg; j++){
		for (int i = 0; i < n; i++){
			parent[j][i] = parent[j-1][parent[j-1][i]];
		}
	}
}

ll Query(int A, int X[], int B, int Y[]){
	// Construct the virtual tree

	// Find all virtual tree nodes
	vector<int> nodes;

	for (int i = 0; i < A; i++){
		nodes.push_back(X[i]);
		color[X[i]] = 0;
	}

	for (int i = 0; i < B; i++){
		nodes.push_back(Y[i]);
		color[Y[i]] = 1;
	}

	auto sort_by_tin = [&](int p1, int p2){
		return tin[p1] < tin[p2];
	};

	sort(nodes.begin(), nodes.end(), sort_by_tin);
	int sz = nodes.size();

	for (int i = 1; i < sz; i++){
		nodes.push_back(LCA(nodes[i-1], nodes[i]));
	}

	sort(nodes.begin(), nodes.end(), sort_by_tin);
	nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());

	sz = nodes.size();
	for (auto i: nodes) reset_queue.push_back(i);

	// Construct the tree
	stack<int> stk;

	for (int i = 0; i < sz; i++){
		int x = nodes[i];
		while (!stk.empty() && tout[x] > tout[stk.top()]) stk.pop();

		if (!stk.empty()){
			int p = stk.top();
			graph[p].push_back(x);
			graph[x].push_back(p);
		}

		stk.push(x);
	}

	// Solve the query
	ll res = inf;
	solve(res, nodes[0]);

	// Reset
	for (auto x: reset_queue){
		graph[x].clear();
		color[x] = -1;
	}
	reset_queue.clear();

	return res;
}

#undef distance

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 852 KB Output is correct
2 Correct 632 ms 18884 KB Output is correct
3 Correct 693 ms 18856 KB Output is correct
4 Correct 662 ms 19004 KB Output is correct
5 Correct 590 ms 19248 KB Output is correct
6 Correct 409 ms 18876 KB Output is correct
7 Correct 677 ms 18852 KB Output is correct
8 Correct 649 ms 19048 KB Output is correct
9 Correct 596 ms 19260 KB Output is correct
10 Correct 415 ms 18904 KB Output is correct
11 Correct 674 ms 18840 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1809 ms 143956 KB Output is correct
3 Correct 2523 ms 145432 KB Output is correct
4 Correct 1227 ms 141128 KB Output is correct
5 Correct 2173 ms 176820 KB Output is correct
6 Correct 2823 ms 147928 KB Output is correct
7 Correct 1379 ms 47224 KB Output is correct
8 Correct 864 ms 47296 KB Output is correct
9 Correct 1085 ms 51908 KB Output is correct
10 Correct 1319 ms 48704 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 852 KB Output is correct
2 Correct 632 ms 18884 KB Output is correct
3 Correct 693 ms 18856 KB Output is correct
4 Correct 662 ms 19004 KB Output is correct
5 Correct 590 ms 19248 KB Output is correct
6 Correct 409 ms 18876 KB Output is correct
7 Correct 677 ms 18852 KB Output is correct
8 Correct 649 ms 19048 KB Output is correct
9 Correct 596 ms 19260 KB Output is correct
10 Correct 415 ms 18904 KB Output is correct
11 Correct 674 ms 18840 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1809 ms 143956 KB Output is correct
14 Correct 2523 ms 145432 KB Output is correct
15 Correct 1227 ms 141128 KB Output is correct
16 Correct 2173 ms 176820 KB Output is correct
17 Correct 2823 ms 147928 KB Output is correct
18 Correct 1379 ms 47224 KB Output is correct
19 Correct 864 ms 47296 KB Output is correct
20 Correct 1085 ms 51908 KB Output is correct
21 Correct 1319 ms 48704 KB Output is correct
22 Correct 2936 ms 154408 KB Output is correct
23 Correct 2875 ms 156152 KB Output is correct
24 Correct 3215 ms 157536 KB Output is correct
25 Correct 3439 ms 161140 KB Output is correct
26 Correct 4086 ms 155636 KB Output is correct
27 Correct 2948 ms 183544 KB Output is correct
28 Correct 1996 ms 154716 KB Output is correct
29 Correct 4582 ms 154980 KB Output is correct
30 Correct 4461 ms 154464 KB Output is correct
31 Correct 4419 ms 155124 KB Output is correct
32 Correct 1084 ms 57736 KB Output is correct
33 Correct 843 ms 50544 KB Output is correct
34 Correct 1155 ms 45104 KB Output is correct
35 Correct 1206 ms 44988 KB Output is correct
36 Correct 1338 ms 45780 KB Output is correct
37 Correct 1375 ms 45656 KB Output is correct