Submission #134686

#	Time	Username	Problem	Language	Result	Execution time	Memory
134686		FedericoS	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1517 ms	29488 KiB

plan

#include <iostream>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef pair<int,int> pii;

int c=0;
int N,M;
int x,y,z;
vector<pii> grafo[100005];
priority_queue<pii> PQ;
int D[100005];
bool V[100005];
vector<pair<int,pii>> E;
int P[100005];
int H[100005];
int W[100005];
vector<int> albero[100005];

int fi(int x){
	while(x!=P[x])
		x=P[x];
	return x;
}

void un(int x, int y, int v){

	x=fi(x);
	y=fi(y);

	if(H[x]<H[y])
		swap(x,y);

	W[y]=v;
	P[y]=x;
	H[x]=max(H[x],H[y]+1);
}

void DFS(int k, int p=-1, int h=0){
	H[k]=h;
	for(int f:albero[k])
		if(f!=p)
			DFS(f,k,h+1);
}

int LCA(int x, int y){

	if(x==y)
		return D[x];

	if(H[y]>H[x])
		swap(x,y);

	while(H[x]-1>H[y])
		x=P[x];

	if(P[x]==y)
		return W[x];
	if(H[x]!=H[y])
		x=P[x];

	assert(H[x]==H[y]);

	while(P[x]!=P[y]){
		x=P[x];
		y=P[y];
	}

	return min(W[x],W[y]);

}

int main(){
	cin>>N>>M;
	for(int i=0;i<M;i++){
		cin>>x>>y>>z;
		x--,y--;
		grafo[x].push_back({y,z});
		grafo[y].push_back({x,z});
	}

	for(int i=0;i<N;i++)
		D[i]=1e9;

	cin>>M;
	for(int i=0;i<M;i++){
		cin>>x;
		x--;
		PQ.push({0,x});
		D[x]=0;
	}

	while(!PQ.empty()){

		x=PQ.top().second;
		PQ.pop();

		if(V[x])
			continue;
		V[x]=true;

		for(pii f:grafo[x])
			if(D[f.first]>D[x]+f.second){
				D[f.first]=D[x]+f.second;
				PQ.push({-D[f.first],f.first});
			}
	}

	for(int i=0;i<N;i++)
		for(pii f:grafo[i])
			if(f.first>i)
				E.push_back({min(D[i],D[f.first]),{i,f.first}});
	sort(E.begin(),E.end(),greater<pair<int,pii>>());

	for(int i=0;i<N;i++)
		P[i]=i;

	for(auto q:E){
		pii p=q.second;
		if(fi(p.first)!=fi(p.second))
			un(p.first,p.second,q.first);
	}

	for(int i=0;i<N;i++)
		if(i!=P[i])
			albero[P[i]].push_back(i);
		else
			M=i;
	DFS(M);

	cin>>M;
	for(int i=0;i<M;i++){
		cin>>x>>y;
		x--,y--;
		cout<<LCA(x,y)<<endl;
	}

}

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