Submission #514702

#	Time	Username	Problem	Language	Result	Execution time	Memory
514702		ymm	Evacuation plan (IZhO18_plan)	C++17	100 / 100	559 ms	58364 KiB

plan

///
///   What would happen if we used assembly language for CP?
///   Sorry, that was a strange thing to ask.
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 200'010;
const int lg = 20;
vector<pii> A[N];
vector<int> B[N];
int dis[N];
pii srt[N];
int n, m, k;

int par[N];
int rt(int v){return par[v]==-1?v:(par[v]=rt(par[v]));}

namespace rmq{
	vector<int> vec;
	int ti[N];
	void dfs(int v){
		ti[v] = vec.size();
		vec.push_back(dis[v]);
		for(int u : B[v]){
			dfs(u);
			vec.push_back(dis[v]);
		}
	}
	int a[lg][N];
	int n;
	void make(){
		n = vec.size();
		Loop(i,0,n) a[0][i] = vec[i];
		Loop(k,0,lg-1)
			for(int i = 0; i+(2<<k) <= n; ++i)
				a[k+1][i] = min(a[k][i], a[k][i+(1<<k)]);
	}
	int get(int l, int r){
		int k = __lg(r-l);
		return min(a[k][l], a[k][r-(1<<k)]);
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	Loop(i,0,N) dis[i] = 1e9;
	Loop(i,0,N) par[i] = -1;
	cin >> n >> m;
	Loop(i,0,m){
		int v, u, w;
		cin >> v >> u >> w;
		--v; --u;
		A[v].push_back({u,w});
		A[u].push_back({v,w});
	}
	cin >> k;
	set<pii> q;
	Loop(i,0,k) {
		int v; cin >> v; --v;
		dis[v] = 0;
		q.emplace(0, v);
	}
	while(q.size()){
		auto [d, v] = *q.begin(); q.erase(q.begin());
		for(auto [u, w] : A[v]){
			if(d+w < dis[u]){
				q.erase({dis[u],u});
				dis[u] = d+w;
				q.insert({dis[u],u});
			}
		}
	}
	Loop(i,0,n) srt[i] = {dis[i],i};
	sort(srt,srt+n,greater<pii>());
	Loop(i,0,n){
		int v = srt[i].second;
		for(auto [u, w] : A[v]){
			if(dis[u] > dis[v] || (dis[u]==dis[v] && u>v)){
				//cout<<v<<' '<<u<<"!"<<endl;
				u = rt(u);
				if(u!=v){
					par[u] = v;
					B[v].push_back(u);
				}
			}
		}
	}
	rmq::dfs(rt(0));
	rmq::make();
	int qq;
	cin >> qq;
	while(qq--){
		int v, u;
		cin >> v >> u;
		--v; --u;
		if(rmq::ti[v] > rmq::ti[u]) swap(v, u);
		cout << rmq::get(rmq::ti[v], rmq::ti[u]+1) << '\n';
	}
}

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