oj.uz

Submission #993742

# Submission time Handle Problem Language Result Execution time Memory
993742 2024-06-06T10:54:40 Z Error42 Factories (JOI14_factories) C++17
0 / 100
 549 ms 96692 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[cur]) {
		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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 16984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18520 KB Output is correct
2 Incorrect 549 ms 96692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 16984 KB Output isn't correct
2 Halted 0 ms 0 KB -