Submission #1279003

#TimeUsernameProblemLanguageResultExecution timeMemory
1279003IBoryFactories (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 500005;
vector<pii> G[MAX], TG[MAX];
int P[MAX][19], H[MAX], in[MAX], T[MAX], dn;
ll D[MAX], ans;

void DFS(int cur, int prev) {
	H[cur] = H[prev] + 1;
	P[cur][0] = prev;
	in[cur] = ++dn;
	for (auto [next, d] : G[cur]) {
		if (next == prev) continue;
		D[next] = D[cur] + d;
		DFS(next, cur);
	}
}

int LCA(int a, int b) {
	if (H[a] < H[b]) swap(a, b);
	for (int i = 18; i >= 0; --i) if ((H[a] - H[b]) & (1 << i)) a = P[a][i];
	if (a == b) return a;
	for (int i = 18; i >= 0; --i) if (P[a][i] != P[b][i]) a = P[a][i], b = P[b][i];
	return P[a][0];
}

pii DFS2(int cur) {
	pii ret = { (ll)1e18, (ll)1e18 };
	if (T[cur]) (T[cur] == 1 ? ret.first : ret.second) = 0;
	for (auto& [next, d] : TG[cur]) {
		auto [nd1, nd2] = DFS2(next);
		ret.first = min(ret.first, nd1 + d);
		ret.second = min(ret.second, nd2 + d);
	}
	ans = min(ans, ret.first + ret.second);
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	for (int i = 1; i < N; ++i) {
		int u, v, d;
		cin >> u >> v >> d;
		G[u].emplace_back(v, d);
		G[v].emplace_back(u, d);
	}

	DFS(0, 0);
	for (int n = 1; n < 19; ++n) for (int i = 0; i < N; ++i) P[i][n] = P[P[i][n - 1]][n - 1];

	while (Q--) {
		int AN, BN;
		cin >> AN >> BN;
		vector<int> A;
		for (int i = 0; i < AN; ++i) {
			int n;
			cin >> n;
			A.push_back(n);
			T[n] = 1;
		}
		for (int i = 0; i < BN; ++i) {
			int n;
			cin >> n;
			A.push_back(n);
			T[n] = 2;
		}

		sort(A.begin(), A.end(), [&](int a, int b) { return in[a] < in[b]; });
		for (int i = 0; i < AN + BN - 1; ++i) A.push_back(LCA(A[i], A[i + 1]));
		sort(A.begin(), A.end(), [&](int a, int b) { return in[a] < in[b]; });
		A.erase(unique(A.begin(), A.end()), A.end());
		for (int i = 1; i < A.size(); ++i) {
			int pv = LCA(A[i], A[i - 1]);
			TG[pv].emplace_back(A[i], D[A[i]] - D[pv]);
		}

		ans = 1e18;
		DFS2(A[0]);
		cout << ans << '\n';

		for (int n : A) {
			T[n] = 0;
			TG[n].clear();
		}
	}

	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccGRcpKs.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccGoIl3z.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccGRcpKs.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