Submission #572152

#	Time	Username	Problem	Language	Result	Execution time	Memory
572152		vovamr	Evacuation plan (IZhO18_plan)	C++17	100 / 100	753 ms	71372 KiB

plan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 1e5 + 100;
ve<pii> gr[N]; ll dist[N];

const int M = 2e5 + 100, lg = 19; int w = 0;
int p[M], val[M]; ve<int> g[M];
inline void build(int n) { w = n; for (int i = 0; i < n; ++i) p[i] = i; }
inline int par(int v) { if (p[v] == v) { return v; } return (p[v] = par(p[v])); }
inline int uni(int a, int b) {
	a = par(a), b = par(b);
	if (a == b) return -1;
	int c = w++; p[a] = p[b] = p[c] = c;
	g[c].pb(a); g[c].pb(b);
	return c;
} int tim = 0;
int in[M], out[M], up[M][lg];
inline void dfs(int v, int p) {
	in[v] = ++tim; up[v][0] = p;
	for (auto &to : g[v]) dfs(to, v);
	out[v] = ++tim;
}
inline bool anc(int a, int b) { return in[a] <= in[b] && out[b] <= out[a]; }
inline int lca(int a, int b) {
	if (anc(a, b)) return a;
	if (anc(b, a)) return b;
	for (int i = lg - 1; ~i; --i) {
		if (!anc(up[a][i], b)) {
			a = up[a][i];
		}
	} return up[a][0];
}

inline void solve() {
	int n, m;
	cin >> n >> m;
	ve<array<ll,3>> e(m);
	for (int i = 0; i < m; ++i) {
		int v, u, w;
		cin >> v >> u >> w, --v, --u;
		gr[v].pb({u, w}), gr[u].pb({v, w});

		e[i] = {v, u, w};
	}
	int k;
	cin >> k;

	fill(dist, dist + n, inf);
	set<pll> st;

	for (int i = 0; i < k; ++i) {
		int v;
		cin >> v;
		st.insert({(dist[--v] = 0), v});
	}
	while (!st.empty()) {
		int v = st.begin()->se;
		st.erase(st.begin());
		for (auto &[to, w] : gr[v]) {
			if (chmin(dist[to], dist[v] + w)) {
				st.insert({dist[to], to});
			}
		}
	}

	for (int i = 0; i < m; ++i) {
		auto &[v, u, w] = e[i];
		e[i] = {min(dist[v], dist[u]), v, u};
	} sort(all(e));
	reverse(all(e));
	
	build(n);
	for (auto &[w, v, u] : e) {
		int c = uni(v, u);
		if (~c) val[c] = w;
	}
	for (int i = 0; i < w; ++i) if (p[i] == i) dfs(i, i);
	for (int i = 1; i < lg; ++i) {
		for (int v = 0; v < w; ++v) {
			up[v][i] = up[up[v][i - 1]][i - 1];
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int v, u;
		cin >> v >> u;
		cout << val[lca(--v, --u)] << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46