oj.uz

Submission #993777

# Submission time Handle Problem Language Result Execution time Memory
993777 2024-06-06T12:08:50 Z Error42 Factories (JOI14_factories) C++17
15 / 100
 7044 ms 524288 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] += 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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1312 KB Output is correct
2 Correct 632 ms 30460 KB Output is correct
3 Correct 834 ms 34768 KB Output is correct
4 Correct 691 ms 31060 KB Output is correct
5 Correct 335 ms 23004 KB Output is correct
6 Correct 145 ms 18768 KB Output is correct
7 Correct 733 ms 34504 KB Output is correct
8 Correct 1135 ms 40328 KB Output is correct
9 Correct 353 ms 22956 KB Output is correct
10 Correct 142 ms 18764 KB Output is correct
11 Correct 760 ms 34128 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Runtime error 7044 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1312 KB Output is correct
2 Correct 632 ms 30460 KB Output is correct
3 Correct 834 ms 34768 KB Output is correct
4 Correct 691 ms 31060 KB Output is correct
5 Correct 335 ms 23004 KB Output is correct
6 Correct 145 ms 18768 KB Output is correct
7 Correct 733 ms 34504 KB Output is correct
8 Correct 1135 ms 40328 KB Output is correct
9 Correct 353 ms 22956 KB Output is correct
10 Correct 142 ms 18764 KB Output is correct
11 Correct 760 ms 34128 KB Output is correct
12 Correct 3 ms 1112 KB Output is correct
13 Runtime error 7044 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -