oj.uz

답안 #993787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993787 2024-06-06T12:26:02 Z Error42 공장들 (JOI14_factories) C++17
100 / 100
 3451 ms 367416 KB 
#include "factories.h"

#include <climits>
#include <vector>

using namespace std;

using ll = long long;

#define int ll

ll const INF = LLONG_MAX / 3;

struct edge {
	ll to, dist;
};

ll n;

ll cur_dist = 0;
vector<vector<edge>> ancestors;
vector<vector<edge>> graph;
vector<ll> sz;
vector<char> removed;
vector<ll> min_dist;

void calc_sz(int const cur, int const par) {
	sz[cur] = 1;

	for (auto const& [neigh, _dist] : graph[cur]) {
		if (removed[neigh] || neigh == par)
			continue;

		calc_sz(neigh, cur);
		sz[cur] += sz[neigh];
	}
}

int get_centroid(int const cur, int const par, int const tree_sz) {
	for (auto const& [neigh, _dist] : graph[cur]) {
		if (removed[neigh] || neigh == par)
			continue;

		if (sz[neigh] > tree_sz / 2)
			return get_centroid(neigh, cur, tree_sz);
	}

	return cur;
}

void calc_ancestors(int const cur, int const par, int const centroid) {
	ancestors[cur].push_back({ centroid, cur_dist });

	for (auto const& [neigh, dist] : graph[cur]) {
		if (removed[neigh] || neigh == par)
			continue;

		cur_dist += dist;
		calc_ancestors(neigh, cur, centroid);
		cur_dist -= dist;
	}
}

void decompose(int const cur) {
	calc_sz(cur, -1);
	int const centroid = get_centroid(cur, -1, sz[cur]);
	calc_ancestors(centroid, -1, centroid);
	removed[centroid] = true;
	
	for (auto const& [neigh, _dist] : graph[centroid]) {
		if (removed[neigh])
			continue;

		decompose(neigh);
	}
}

void Init(signed const N, signed a[], signed b[], signed d[]) {
	n = N;

	graph.resize(n);
	sz.resize(n);
	removed.resize(n);
	ancestors.resize(n);
	min_dist.assign(n, INF);

	for (int i = 0; i < n - 1; i++) {
		graph[a[i]].push_back({ b[i], d[i] });
		graph[b[i]].push_back({ a[i], d[i] });
	}

	decompose(0);
}

ll Query(signed const s, signed x[], signed const t, signed y[]) {
	for (int i = 0; i < t; i++) {
		int const cur = y[i];

		for (auto const& [ancestor, dist] : ancestors[cur]) {
			min_dist[ancestor] = min(min_dist[ancestor], dist);
		}
	}

	ll ans = INF;
	
	for (int i = 0; i < s; i++) {
		int const cur = x[i];

		for (auto const& [ancestor, dist] : ancestors[cur]) {
			ans = min(ans, min_dist[ancestor] + dist);
		}
	}

	for (int i = 0; i < t; i++) {
		int const cur = y[i];

		for (auto const& [ancestor, dist] : ancestors[cur]) {
			min_dist[ancestor] = INF;
		}
	}

	return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 856 KB Output is correct
2 Correct 184 ms 19280 KB Output is correct
3 Correct 210 ms 19540 KB Output is correct
4 Correct 215 ms 19540 KB Output is correct
5 Correct 214 ms 20312 KB Output is correct
6 Correct 137 ms 18772 KB Output is correct
7 Correct 199 ms 19692 KB Output is correct
8 Correct 214 ms 19792 KB Output is correct
9 Correct 211 ms 20004 KB Output is correct
10 Correct 138 ms 18692 KB Output is correct
11 Correct 196 ms 19740 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1591 ms 216388 KB Output is correct
3 Correct 2453 ms 285924 KB Output is correct
4 Correct 541 ms 110160 KB Output is correct
5 Correct 2959 ms 361020 KB Output is correct
6 Correct 2617 ms 287524 KB Output is correct
7 Correct 515 ms 64340 KB Output is correct
8 Correct 220 ms 41404 KB Output is correct
9 Correct 647 ms 78676 KB Output is correct
10 Correct 595 ms 65784 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 856 KB Output is correct
2 Correct 184 ms 19280 KB Output is correct
3 Correct 210 ms 19540 KB Output is correct
4 Correct 215 ms 19540 KB Output is correct
5 Correct 214 ms 20312 KB Output is correct
6 Correct 137 ms 18772 KB Output is correct
7 Correct 199 ms 19692 KB Output is correct
8 Correct 214 ms 19792 KB Output is correct
9 Correct 211 ms 20004 KB Output is correct
10 Correct 138 ms 18692 KB Output is correct
11 Correct 196 ms 19740 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1591 ms 216388 KB Output is correct
14 Correct 2453 ms 285924 KB Output is correct
15 Correct 541 ms 110160 KB Output is correct
16 Correct 2959 ms 361020 KB Output is correct
17 Correct 2617 ms 287524 KB Output is correct
18 Correct 515 ms 64340 KB Output is correct
19 Correct 220 ms 41404 KB Output is correct
20 Correct 647 ms 78676 KB Output is correct
21 Correct 595 ms 65784 KB Output is correct
22 Correct 1788 ms 221552 KB Output is correct
23 Correct 1905 ms 226640 KB Output is correct
24 Correct 2855 ms 293712 KB Output is correct
25 Correct 2994 ms 297852 KB Output is correct
26 Correct 2899 ms 295016 KB Output is correct
27 Correct 3451 ms 367416 KB Output is correct
28 Correct 622 ms 120492 KB Output is correct
29 Correct 2819 ms 294012 KB Output is correct
30 Correct 2841 ms 294484 KB Output is correct
31 Correct 2660 ms 293860 KB Output is correct
32 Correct 701 ms 79008 KB Output is correct
33 Correct 221 ms 41876 KB Output is correct
34 Correct 360 ms 56832 KB Output is correct
35 Correct 397 ms 57680 KB Output is correct
36 Correct 523 ms 62600 KB Output is correct
37 Correct 548 ms 62800 KB Output is correct