Submission #378530

#	Time	Username	Problem	Language	Result	Execution time	Memory
378530		iris2617	Evacuation plan (IZhO18_plan)	C++14	100 / 100	798 ms	59904 KiB

plan

#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
#define iris 1000000007
using namespace std;

vector<matsuri> G[100010];
int dis[100010];
priority_queue<matsuri, vector<matsuri>, greater<matsuri> > pq;
int id[100010];
bitset<100010> v;

int x;
set<int> s[100010];
int ds[100010],sz[100010],ans[100010];

bool cmp(int a,int b)
{
	return dis[a]>dis[b];
}

int fnd(int a)
{
	return ds[a] = ds[a]==a ? a : fnd(ds[a]);
}

void unn(int a,int b)
{
	a=fnd(a);
	b=fnd(b);
	if(a==b)
		return;
	if(sz[a]<sz[b])
		swap(a,b);
	ds[b]=a;
	sz[a]+=sz[b];
	for(int sana:s[b])
	{
		if(s[a].find(sana)==s[a].end())
			s[a].insert(sana);
		else
		{
			s[a].erase(sana);
			ans[sana]=x;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,m,a,b,c,k,i,q;
	
	cin>>n>>m;
	while(m--)
	{
		cin>>a>>b>>c;
		G[a].emplace_back(b,c);
		G[b].emplace_back(a,c);
	}
	for(i=1;i<=n;i++)
	{
		dis[i]=1e15;
		id[i]=i;
		ds[i]=i;
		sz[i]=1;
	}
	cin>>k;
	for(i=0;i<k;i++)
	{
		cin>>a;
		dis[a]=0;
		pq.push({0,a});
	}
	while(!pq.empty())
	{
		a=pq.top().second;
		c=pq.top().first;
		pq.pop();
		if(c!=dis[a])
			continue;
		for(auto sana:G[a])
		{
			b=sana.first;
			c=sana.second;
			if(dis[a]+c<dis[b])
			{
				dis[b]=dis[a]+c;
				pq.push({dis[b], b});
			}
		}
	}
	sort(id+1,id+1+n,cmp);
	cin>>q;
	for(i=1;i<=q;i++)
	{
		cin>>a>>b;
		s[a].insert(i);
		s[b].insert(i);
	}
	for(i=1;i<=n;i++)
	{
		a=id[i];
		v[a]=1;
		x=dis[a];
		for(auto sana:G[a])
		{
			b=sana.first;
			if(v[b])
			{
				unn(a,b);
			}
		}
	}
	for(i=1;i<=q;i++)
	{
		cout<<ans[i]<<'\n';
	}
	
	return 0;
}

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