Submission #77083

#	Time	Username	Problem	Language	Result	Execution time	Memory
77083		zetapi	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1144 ms	89400 KiB

plan

#include "bits/stdc++.h"
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define int long long
#define itr iterator
 
typedef pair<int,int> pii;
 
const int MAX=2e5;
const int INF=1e12;
 
vector<pair<int,pii>> edge;
 
vector<pii> adj[MAX];
vector<int> vec[MAX];
 
int N,M,K,Q,X,Y,Z,arr[MAX],wei[MAX],hei[MAX],Value[MAX][20],Parent[MAX][20];
int par[MAX],rank_[MAX];
 
void init()
{
	for(int A=1;A<=N;A++)
	{
		par[A]=A;
		rank_[A]=0;
	}
	return ;
}
 
int root(int X)
{
	if(par[X]==X)
		return X;
	return par[X]=root(par[X]);
}
 
void unions(int X,int Y)
{
	int u=root(X),v=root(Y);
	if(u==v)
		return ;
	vec[X].pb(Y);
	vec[Y].pb(X);
	if(rank_[u]<rank_[v])
		par[u]=v;
	else if(rank_[v]<rank_[u])
		par[v]=u;
	else
	{
		par[u]=v;
		rank_[v]++;
	}
	return ;
}
 
void dfs(int node,int par)
{
	assert(Parent[node][0]==0);
	Parent[node][0]=par;
	Value[node][0]=min(wei[node],wei[par]);
	assert(Value[node][0]!=INF);
	for(auto A:vec[node])
	{
		if(A==par)
			continue;
		hei[A]=hei[node]+1;
		dfs(A,node);
	}
	return ;
}
 
void dijkstra()
{
	int vis[MAX];
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int A=0;A<=N;A++)
	{
		vis[A]=0;
		wei[A]=INF;
	}
	for(int A=1;A<=K;A++)
	{
		wei[arr[A]]=0;
		pq.push(mp(0,arr[A]));
	}
	while(!pq.empty())
	{
		pii cur=pq.top();
		pq.pop();
		if(vis[cur.second])
			continue;
		vis[cur.second]=1;
		for(auto A:adj[cur.second])
		{
			if(A.second+cur.first<wei[A.first])
			{
				wei[A.first]=A.second+cur.first;
				pq.push(mp(wei[A.first],A.first));
			}
		}
	}
	return ;
}
 
int lca(int X,int Y)
{
	if(hei[X]>hei[Y])
		swap(X,Y);
	int dis=hei[Y]-hei[X];
	for(int A=19;A>=0;A--)
		if(dis&(1<<A))
			dis-=(1<<A),
			Y=Parent[Y][A];
	assert(dis==0);
	assert(hei[X]==hei[Y]);
	if(X==Y)
		return X;
	for(int A=19;A>=0;A--)
	{
		if(Parent[X][A]!=Parent[Y][A])
		{
			X=Parent[X][A];
			Y=Parent[Y][A];
		}
	}
	assert(Parent[X][0]==Parent[Y][0]);
	return Parent[X][0];
}
 
int query(int X,int Y)
{
	int res=INF;
	for(int A=19;A>=0;A--)
	{
		if(hei[Parent[X][A]]>=hei[Y])
		{
			res=min(res,Value[X][A]);
			X=Parent[X][A];
		}
	}
	return res;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
 
	cin>>N>>M;
	for(int A=1;A<=M;A++)
	{
		cin>>X>>Y>>Z;
		adj[X].pb(mp(Y,Z));
		adj[Y].pb(mp(X,Z));
		edge.pb(mp(Z,mp(X,Y)));
	}
	cin>>K;
	for(int A=1;A<=K;A++)
		cin>>arr[A];
	dijkstra();
	/*for(int A=1;A<=N;A++)
		cout<<"shortest distance for node "<<A<<" is "<<wei[A]<<"\n";*/
	for(int A=0;A<edge.size();A++)
		edge[A].first=min(wei[edge[A].second.first],wei[edge[A].second.second]);
	sort(edge.begin(),edge.end());
	reverse(edge.begin(),edge.end());
	init();
	for(auto A:edge)
		unions(A.second.first,A.second.second);
	dfs(1,0);
	for(int A=2;A<=N;A++)
		assert(Parent[A][0]!=0);
	for(int A=0;A<20;A++)
		Value[0][A]=INF;
	for(int A=1;A<20;A++)
	{
		for(int B=1;B<=N;B++)
		{
			Parent[B][A]=Parent[Parent[B][A-1]][A-1];
			Value[B][A]=min(Value[B][A-1],Value[Parent[B][A-1]][A-1]);
		}
	}
	cin>>Q;
	while(Q--)
	{
		cin>>X>>Y;
		int cur=lca(X,Y);
		cout<<min(query(X,cur),query(Y,cur))<<"\n";
	}
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:164:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<edge.size();A++)
              ~^~~~~~~~~~~~

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