Submission #886210

#	Time	Username	Problem	Language	Result	Execution time	Memory
886210		javotaz	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KiB

factories

// In the Name of Allah
 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
#define cln(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define unq(a, n); {vector<int> v; for(int i = 0; i < n; i++) v.pb(a[i]); cln(v); for (int i = 0; i < n; i++) a[i] = lower_bound(all(v), a[i]) - v.begin();}

const int N = 5e5 + 12, inf = 1e18 + 12;
vector<pii> g[N];
int sz[N], val[N], cpar[N], q, n;
set<pii> cdis[N];
bool mrk[N];
vector<int> a, b;

void dfs(int u, int par = -1) {
	sz[u] = 1;
	for (auto i: g[u])
		if (i.F != par && !mrk[i.F]) {
			dfs(i.F, u);
			sz[u] += sz[i.F];
		}
}

int find_centroid(int u, int c, int par = -1) {
	for (auto i: g[u])
		if (!mrk[i.F] && i.F != par && sz[i.F] > (c - 1) / 2)
			return find_centroid(i.F, c, u);
	return u;
}

void fill_cdis(int u, int cent, int c = 0, int par = -1) {
	cdis[cent].insert({u, c});
	for (auto i: g[u])
		if (!mrk[i.F] && i.F != par)
			fill_cdis(i.F, cent, c + i.S, u);
}

void decompose(int u, int par = -1) {
	dfs(u);
	u = find_centroid(u, sz[u]);
	fill_cdis(u, u);
	cpar[u] = par;
	mrk[u] = true;
	for (auto i: g[u])
		if (!mrk[i.F])
			decompose(i.F, u);
}

void ip() {
	cin >> n >> q;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
}

void pre() {
	decompose(0);
	fill(val, val + n, inf);
}

void ipq() {
	int ca, cb;
	cin >> ca >> cb;
	a.resize(ca), b.resize(cb);
	for (int i = 0; i < ca; i++)
		cin >> a[i];
	for (int i = 0; i < cb; i++)
		cin >> b[i];
}

void add(int u, int v) {
	if (u == -1)
		return;
	val[u] = min(val[u], cdis[u].lower_bound({v, -1})->S);
	add(cpar[u], v);
}

int ask(int u, int v) {
	if (u == -1)
		return inf;
	int tmp = cdis[u].lower_bound({v, -1})->S;
	return min(ask(cpar[u], v), tmp + val[u]);
}

void rem(int u) {
	val[u] = inf;
	if (cpar[u] != -1)
		rem(cpar[u]);
}

void query() {
	while (q--) {
		ipq();
		for (auto i: a)
			add(i, i);
		int res = inf;
		for (auto i: b)
			res = min(res, ask(i, i));
		cout << res << '\n';
		for (auto i: a)
			rem(i);
		a.clear(), b.clear();
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), pre(), query();
	return 0;
}

Compilation message (stderr)

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