Submission #342262

#	Time	Username	Problem	Language	Result	Execution time	Memory
342262		ogibogi2004	Evacuation plan (IZhO18_plan)	C++14	100 / 100	871 ms	48712 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define fi first
#define se second
const int MAXN=1e5+6;
const int MAXM=5e5+6;
const int INF=2e9;
vector<pair<int,int> >g[MAXN];
struct edge
{
	int u,v;
	int w;
	bool operator<(edge const& other)const
	{
		return w>other.w;
	}
}e[MAXM];
int n,m,k;
int d[MAXN];
vector<int>q;
int l[MAXN],r[MAXN];
int s[MAXN],t[MAXN];
int par[MAXN],sz[MAXN];
bool used[MAXN];
vector<int>to_check[MAXM];
void dijkstra()
{
	priority_queue<pp,vector<pp>,greater<pp> >pq;
	for(auto xd:q)
	{
		pq.push({0,xd});
		d[xd]=0;
	}
	while(!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		if(used[u])continue;
		used[u]=1;
		for(auto v:g[u])
		{
			if(d[u]+v.second<d[v.first])
			{
				d[v.first]=v.second+d[u];
				pq.push({d[v.first],v.first});
			}
		}
	}
}
int getRoot(int u)
{
	if(u==par[u])return u;
	return par[u]=getRoot(par[u]);
}
void join(int u,int v)
{
	if(sz[u]>sz[v])
	{
		sz[u]+=sz[v];
		par[v]=u;
	}
	else
	{
		sz[v]+=sz[u];
		par[u]=v;
	}
}
void add_edge(edge eksdi)
{
	int u=getRoot(eksdi.u);
	int v=getRoot(eksdi.v);
	if(u!=v)join(u,v);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;++i)
	{
		int w;
		cin>>e[i].u>>e[i].v>>w;
		g[e[i].u].push_back({e[i].v,w});
		g[e[i].v].push_back({e[i].u,w});
	}
	for(int i=1;i<=n;++i)
	{
		d[i]=INF;
	}
	cin>>k;
	for(int i=1;i<=k;++i)
	{
		int x;
		cin>>x;
		q.push_back(x);
	}
	dijkstra();
	for(int i=0;i<m;++i)
	{
		e[i].w=min(d[e[i].v],d[e[i].u]);
	}
	sort(e,e+m);
	cin>>k;
	for(int i=1;i<=k;++i)
	{
		l[i]=0;r[i]=m-1;
		cin>>s[i]>>t[i];
	}
	for(int step=0;step<20;++step)
	{
		for(int i=1;i<=k;++i)
		{
			if(l[i]==r[i])continue;
			int mid=(l[i]+r[i])/2;
			to_check[mid].emplace_back(i);
		}
		for(int i=1;i<=n;++i)
		{
			par[i]=i;sz[i]=1;
		}
		for(int i=0;i<m;++i)
		{
			add_edge(e[i]);
			for(auto xd:to_check[i])
			{
				int u=getRoot(s[xd]);
				int v=getRoot(t[xd]);
				if(u==v)r[xd]=i;
				else l[xd]=i+1;
			}
			to_check[i].clear();
		}
	}
	for(int i=1;i<=k;++i)
	{
		cout<<e[l[i]].w<<"\n";
	}
return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7 
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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