Submission #1211693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211693		catch_me_if_you_can	Evacuation plan (IZhO18_plan)	C++20	100 / 100	306 ms	34392 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 1e5+5;
const int INF = 1e9;
const int LOGM = 17;

vector<in> adj[MX];

vector<int> pa(MX, -1);

vector<in> st(MX);//store label of guy with minimum stuff.

int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
		return pa[u] = leader(pa[u]);
}

void merge(int u, int v)
{
	u = leader(u);
	v = leader(v);
	if(u == v)
		return;
	if(pa[u] < pa[v])
		swap(u, v);
	pa[v]+=pa[u];
	st[v] = min(st[v], st[u]);
	pa[u] = v;
	return;
}

int p[LOGM][MX];

vector<int> adg[MX];

vector<int> tin(MX), tout(MX);

int TIMER;

void dfs(int u)
{
	tin[u] = ++TIMER;
	for(int v: adg[u])
		dfs(v);
	tout[u] = TIMER;
	return;
}

int lca(int u, int v)
{
	if(tin[u] > tin[v])
		swap(u, v);
	if(tout[u] >= tout[v])
		return u;
	for(int x = LOGM-1; x >= 0; x--)
	{
		if(tout[p[x][u]] < tout[v])
			u = p[x][u]; 
	}
	return p[0][u];
}

signed main()
{
	fast();
	int n, m; cin >> n >> m;
	while(m--)
	{
		int u, v, w; cin >> u >> v >> w;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}
	vector<int> cop(n+1);
	vector<in> sp(n+1); sp[0] = {INF, INF};
	for(int i = 1; i <= n; i++)
	{
		sp[i][0] = INF;
		sp[i][1] = i;
	}

	set<in> dij;
	int k; cin >> k;
	while(k--)
	{
		int g; cin >> g;
		dij.insert({0, g});
		sp[g][0] = 0;
	}

	while(dij.size())
	{
		auto [D, u] = *dij.begin();
		dij.erase(dij.begin());
		for(auto [v, w]: adj[u])
		{
			if(sp[v][0] > (D+w))
			{
				dij.erase(sp[v]);
				sp[v][0] = D+w;
				dij.insert(sp[v]);
			}
		} 
	}

	for(int i = 1; i <= n; i++)
	{
		cop[i] = sp[i][0];
		//cout << "Infection distance for " << i << " = " << cop[i] << endl;
		st[i] = sp[i];
	}

	sort(sp.rbegin(), sp.rend());
	vector<bool> done(n+1, false);
	int root;
	for(int i = 1; i <= n; i++)
	{
		auto [D, u] = sp[i];
		done[u] = true;
		root = u;
		for(auto [v, w]: adj[u])
		{
			if(!done[v])
				continue;
			if(leader(u) == leader(v))
				continue;
			int s = st[leader(v)][1];
			p[0][s] = u; adg[u].pb(s);
			merge(u, v);
		}
	}

	p[0][root] = 0;
	p[0][0] = 0;
	tin[0] = 0;
	tout[0] = INF;
	
	dfs(root);
	for(int x = 1; x < LOGM; x++)
	{
		for(int i = 0; i <= n; i++)
			p[x][i] = p[x-1][p[x-1][i]];
	}

	int q; cin >> q;
	while(q--)
	{
		int s, t; cin >> s >> t;
		cout << cop[lca(s, t)] << "\n";
	}

	return 0;
}	

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