Submission #1329164

#TimeUsernameProblemLanguageResultExecution timeMemory
1329164yonatanlFactories (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <iomanip>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

const ll INF = 1e18;

vvpll tree;
vll is_removed;
vll sz, min_dist;
vvpll ancestors;

//vvll par;

/*
ll LCA(ll a, ll b) {
	if (depth[b] > depth[a]) swap(a, b);
	for (ll i = 30 - 1; i >= 0; i--) {
		if (par[i][a] != -1 && depth[par[i][a]] >= depth[b]) {
			a = par[i][a];
		}
	}
}

ll calc_dist(ll a, ll b) {
	return depth[a] + depth[b] - 2 * LCA(a, b);
}*/

ll get_centroid(ll node, ll papa, ll cur_sz) {
	for (auto& it : tree[node]) {
		ll nei = it.first;
		if (nei == papa || is_removed[nei]) continue;
		if (sz[nei] > cur_sz / 2) {
			return get_centroid(nei, node, cur_sz);
		}
	}
	return node;
}

ll get_subtree_size(ll node, ll papa) {
	sz[node] = 1;
	for (auto& it : tree[node]) {
		ll nei = it.first;
		if (nei == papa || is_removed[nei]) continue;
		sz[node] += get_subtree_size(nei, node);
	}
	return sz[node];
}

void get_dists(ll node, ll centroid, ll papa, ll cur_dist) {
	for (auto& it : tree[node]) {
		ll nei = it.first, w = it.second;
		if (nei == papa || is_removed[nei]) continue;
		get_dists(nei, centroid, node, cur_dist + w);
	}
	ancestors[node].push_back({ centroid, cur_dist });
}

void centroid_decomp(ll node) {
	ll cur_sz = get_subtree_size(node, -1);
	ll centroid = get_centroid(node, -1, cur_sz);
	is_removed[centroid] = true;
	for (auto& it : tree[centroid]) {
		ll nei = it.first, w = it.second;
		if (is_removed[nei]) continue;
		get_dists(nei, centroid, centroid, w);
		centroid_decomp(nei);
	}
}

void update(ll node) {
	min_dist[node] = 0;
	rep(i, 0, ancestors[node].size()) {
		ll ancestor = ancestors[node][i].first;
		ll dist = ancestors[node][i].second;
		upmin(min_dist[ancestor], dist);
	}
}

ll query(ll node) {
	ll res = min_dist[node];
	rep(i, 0, ancestors[node].size()) {
		ll ancestor = ancestors[node][i].first;
		ll dist = ancestors[node][i].second;
		upmin(res, min_dist[ancestor] + dist);
	}
	return res;
}

void solve() {
	ll n, q;
	cin >> n >> q;
	tree.clear(), tree.resize(n);
	is_removed.clear(), is_removed.resize(n);
	sz.clear(), sz.resize(n);
	ancestors.clear(), ancestors.resize(n);
	min_dist.clear(), min_dist.resize(n, INF);
	rep(i, 0, n - 1) {
		ll a, b, c;
		cin >> a >> b >> c;
		tree[a].push_back({ b, c });
		tree[b].push_back({ a, c });
	}
	centroid_decomp(0);
	/*while (q--) {
		ll type, node;
		cin >> type >> node;
		node--;
		if (type == 1) update(node);
		else {
			cout << query(node) << endl;
		}
	}*/
	while (q--) {
		ll sz_a, sz_b;
		cin >> sz_a >> sz_b;
		ll ans = INF;
		rep(i, 0, sz_a) {
			ll node;
			cin >> node;
			update(node);
		}
		rep(i, 0, sz_b) {
			ll node;
			cin >> node;
			upmin(ans, query(node));
		}
		cout << ans << endl;
		fill(min_dist.begin(), min_dist.end(), INF);
	}
}

/*
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5
*/

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll t = 1;
	while (t--) {
		solve();
	}
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cca8NIMD.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccL0X337.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cca8NIMD.o: in function `main':
grader.cpp:(.text.startup+0x3b0): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x43b): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status