Submission #1292538

#TimeUsernameProblemLanguageResultExecution timeMemory
1292538sonarchtFactories (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef map<ll,ll> mll;
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll N = 1e5 + 6, inf = 1e18 + 7, mod = 1e9 + 7;
ll n, m, k, q, ans, a[N];

vector<pll> adj[N];
ll p[N], timer = 0, tin[N], tout[N], d[N], up[N][21], mx[N][21];
void dfs(ll p, ll u) {
	tin[u] = ++timer;
	for (auto [v,w] : adj[u]) {
		if (v == p) continue;
		d[v] = d[u] + w; 
		up[v][0] = u;
		mx[v][0] = w;
		for (int j = 1; j <= 20; ++j) {
			up[v][j] = up[up[v][j-1]][j-1];
			mx[v][j] = max(mx[up[v][j-1]][j-1], mx[v][j-1]);
		}
		dfs(u, v);
	}
	tout[u] = timer;
}

bool is_anc(ll u, ll v) {
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}

ll lca(ll u, ll v) {
	if (is_anc(u, v)) return u;
	if (is_anc(v, u)) return v;
	for (int j = 20; j >= 0; --j) {
		if (up[u][j] && !is_anc(up[u][j], v)) u = up[u][j];
	}
	return up[u][0];
}

vector<pll> aux[N];
ll mark[N], dist[N];
priority_queue<pll, vector<pll>, greater<pll>> pq;
bool cmp(ll a, ll b) {
	return tin[a] < tin[b];
}

void dijkstra(vll& v) {
	for (ll s : v) {
		dist[s] = 0;
		pq.push({0, s});
	}
	while (!pq.empty()) {
		auto [d, u] = pq.top();
		pq.pop();
		if (dist[u] != d) continue;
		for (auto [v,w] : aux[u]) {
			if (d+w < dist[v]) {
				dist[v] = d+w;
				pq.push({d+w, v});
			}
		}
	}
}

void solve() {
	cin >> n >> q;
	for (int i = 1; i < n; ++i) {
		ll x, y, w;
		cin >> x >> y >> w;
		++x, ++y;
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}
	dfs(-1, 1);
	fill(dist, dist+N, inf);
	while (q--) {
		ll s, t;
		cin >> s >> t;
		vll v, v1, v2;
		for (int i = 1; i <= s; ++i) {
			ll x;
			cin >> x;
			++x;
			v.push_back(x);
			v1.push_back(x);
			mark[x] = 1;
		}
		for (int i = 1; i <= t; ++i) {
			ll x;
			cin >> x;
			++x;
			v.push_back(x);
			v2.push_back(x);
			mark[x] = 2;
		}
		sort(v.begin(), v.end(), cmp);
		for (ll i = 0; i < s+t-1; ++i) v.push_back(lca(v[i], v[i+1]));
		sort(v.begin(), v.end(), cmp);
		v.erase(unique(v.begin(), v.end()), v.end());
		stack<ll> st;
		for (ll u : v) {
			while (!st.empty() && !is_anc(st.top(), u)) st.pop();
			if (!st.empty()) {
				ll p = st.top(), w = d[u] - d[p];
				aux[u].push_back({p, w});
				aux[p].push_back({u, w});
			}
			st.push(u);
		}
		dijkstra(v1);
		ans = inf;
		for (ll u : v) {
			if (mark[u] == 2) ans = min(ans, dist[u]);
		}
		cout << ans << endl;
		for (ll u : v) {
			aux[u].clear();
			mark[u] = 0;
			dist[u] = inf;
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	if (fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	ll testCase = 1;
//	cin >> testCase;
	while (testCase--) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

factories.cpp: In function 'int main()':
factories.cpp:130:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
factories.cpp:131:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc97wFuy.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccXYAz92.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc97wFuy.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