제출 #1305124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305124		neonglitch	Evacuation plan (IZhO18_plan)	C++20	100 / 100	501 ms	53216 KiB

plan

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int sp[N],dis[N],ord[N],par[N],ans[N];
vector<pair<int,int>> ma[N];
set<int> qry[N];
int get(int x)
{
	return (par[x]==x)?x:par[x]=get(par[x]);
}
void merge(int x,int y)
{
	int ox=x,oy=y;
	x=get(x);
	y=get(y);
	if(x==y)return;
	if(qry[y].size()>qry[x].size())swap(y,x);
	for(auto j:qry[y])
	{
		if(qry[x].find(j)!=qry[x].end())
		{
			ans[j]=min(dis[ox],dis[oy]);
			qry[x].erase(j);
		}
		else{
			qry[x].insert(j);
		}
	}
	par[y]=x;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,k;
	cin>>n>>m;
	
	for(int i=0;i<m;i++)
	{
		int a,b,w;
		cin>>a>>b>>w;
		ma[b].push_back({a,w});
		ma[a].push_back({b,w});
	}
	for(int i=1;i<=n;i++)
	{
		dis[i]=1e9;
	}
	cin>>k;
	priority_queue<pair<ll,int>,vector<pair<ll,int>> ,greater<pair<ll,int>>>pq;
	for(int i=0;i<k;i++)
	{
		cin>>sp[i];
		dis[sp[i]]=0;
		pq.push({0,sp[i]});
	}
	while(pq.size()>0)
	{
		auto it=pq.top();
		pq.pop();
		ll d=it.first;
		int x=it.second;
		if(dis[x]!=d)continue;
		for(auto [y,w]:ma[x])
		{
			if(dis[y]>d+w)
			{
				dis[y]=d+w;
				pq.push({d+w,y});
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		ord[i]=i+1;
	}
	sort(ord,ord+n,[&](int a,int b){return dis[a]<dis[b];});
	reverse(ord,ord+n);
	int q;
	cin>>q;
	for(int j=0;j<q;j++)
	{
		int l,r;
		cin>>l>>r;
		qry[l].insert(j);
		qry[r].insert(j);
	}
	for(int i=1;i<=n;i++)
	{
		par[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		int x=ord[i];
		par[x]=x;
		for(auto [y,w]:ma[x])
		{
			if(par[y])merge(x,y);
		}
	}
	for(int j=0;j<q;j++)
	{
		cout<<ans[j]<<endl;
	}
}

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