Submission #88653

#	Time	Username	Problem	Language	Result	Execution time	Memory
88653		dimash241	Evacuation plan (IZhO18_plan)	C++17	100 / 100	854 ms	72476 KiB

plan

# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 1e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
bool u[N];
int tin[N], tout[N], timer;
vector < pair < int, int > > g[N], gr[N];
vector < pair < int, pair < int, int > > > all;
int d[N], mx[N][22], pr[N][22];
int p[N], sz[N];

int get (int a) {
	if (a == p[a]) return a;
	return p[a] = get(p[a]);
}

bool uni (int a, int b) {
	a = get(a), b = get(b);

	if (a == b) return 0;
	if (sz[a] > sz[b]) swap(a, b);
	sz[b] += sz[a];
	p[a] = b;
	return 1;
}

void dfs (int v) {
	u[v] = 1;
	tin[v] = ++ timer;
	For (i, 1, 18) {
		pr[v][i] = pr[pr[v][i - 1]][i - 1];
		mx[v][i] = min(mx[v][i - 1], mx[pr[v][i - 1]][i - 1]);
	}

	for (auto to : gr[v]) {
		if (!u[to.F]) {
			mx[to.F][0] = to.S;
			pr[to.F][0] = v;
			dfs (to.F);            
		}
	}

	tout[v] = timer;
}

bool upper (int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int lca (int a, int b) {
	if (upper(a, b)) return a;
	if (upper(b, a)) return b;

	for (int i = 18; i >= 0; i --) {
		if (!upper(pr[a][i], b))
			a = pr[a][i];
	}

	return pr[a][0];
}

int get (int a, int b) {
	int res = inf;
	if (a == b) return res;

	for (int i = 18; i >= 0; i --) {
		if (!upper(pr[a][i], b)) {
			res = min(res, mx[a][i]);
			a = pr[a][i];
		}
	}

	return min(res, mx[a][0]);
}


int main () {
	SpeedForce;
	// freopen("out", "w", stdout);               
	cin >> n >> m;
	tout[0] = inf;
	For (i, 1, m) {
		int l, r, x;
		cin >> l >> r >> x;
		g[l].pb(mp(r, x));
		g[r].pb(mp(l, x));
		all.pb(mp(x, mp(l, r)));
	}

	set < pair < int, int > > s;

	cin >> k;
	for (int i = 1; i <= n; i ++) {
		d[i] = inf;
		p[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= k; i ++) {
		int x;
		cin >> x;
		s.insert(mp(0, x));
		d[x] = 0;
	}

	while (s.size()) {
		int v = s.begin() -> S;
		s.erase(s.begin());

		for (auto to : g[v]) {
			if (d[to.F] > d[v] + to.S) {
				s.erase(mp(d[to.F], to.F));
				d[to.F] = d[v] + to.S;
				s.insert(mp(d[to.F], to.F));
			}
		}
	}
	for (auto &it : all) {
		
		it.F = min(d[it.S.F], d[it.S.S]);
	}
	sort(every(all));
	reverse(every(all));

	for (auto it : all) {
		if (uni(it.S.F, it.S.S)) {
			gr[it.S.F].pb(mp(it.S.S, it.F));
			gr[it.S.S].pb(mp(it.S.F, it.F));
		//	cout << it.S.F << ' ' << it.S.S << ' ' <<  << '\n';
		}
	}       

	dfs (1);

	int q;
	cin >> q;
	while (q -- ) {
		int l, r;
		cin >> l >> r;

		int x = lca(l, r);
	//	cout << x << ' ' << l << ' ' << r << " query " << get(l, x) << ' ' << get(r, x) << ' ' ;

		cout << min(get(l, x), get(r, x)) << '\n';
	}

    return Accepted;
}

// Coded By OB

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