제출 #1041157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041157		nguyenletrung	Evacuation plan (IZhO18_plan)	C++14	0 / 100	100 ms	52956 KiB

plan

#include<bits/stdc++.h>
using namespace std;
long long const maxn=2000005;
long long n,m,k,qn,d[200005],ans[200005],l[100005],r[100005],pr[100005],sz[100005];
vector<pair<int,int>> adj[200005];
bool  vis[100005];
pair<int,int> cau[100005],hoi[100005];
pair<int,int> v[100005];
vector<int> event[100005];

int find(int u)
{
	if(pr[u]==u) return u;
	else return find(pr[u]);
}
void uni(int u,int v)
{
	if((u=find(u))==(v=find(v))) return;
	if(sz[u]<sz[v]) swap(u,v);
	sz[u]+=sz[v];
	pr[v]=u;
}
//map<pair<int,int>,int> mp;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		d[i]=1e18;
	}
	for(int i=1;i<=m;i++)
	{
		long long x,y,z;
		cin>>x>>y>>z;
		v[i].first=x;
		v[i].second=y;
		adj[x].push_back({y,z});
		adj[y].push_back({x,z});
	}
	priority_queue<pair<int,int>> q;
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int x;cin>>x;
		q.push({0,x});
		d[x]=0;
	}
	while(!q.empty())
	{
		int a=q.top().second;q.pop();
		if(vis[a]) continue;
		else vis[a]=true;
		for(auto x:adj[a])
		{
			int b=x.first,c=x.second;
			if(d[b]>d[a]+c)
			{
				d[b]=d[a]+c;
				q.push({-d[b],b});
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<d[i]<<' ';
	}
	cout<<endl;
	vector<pair<int,pair<int,int>>> tt;
	for(int i=1;i<=m;i++)
	{
		long long vl=min(d[v[i].first],d[v[i].second]);
		tt.push_back({vl,{v[i].first,v[i].second}});
	}
	cin>>qn;
	for(int i=1;i<=qn;i++)
	{
		cin>>hoi[i].first>>hoi[i].second;
	}
//	cout<<endl;
	sort(tt.begin(),tt.end(),greater<pair<int,pair<int,int>>>());
	for(int i=1;i<=m;i++)
	{
		cau[i].first=tt[i-1].second.first;
		cau[i].second=tt[i-1].second.second;
//		cout<<cau[i].first<<' '<<cau[i].second<<endl;
	}
	for(int i=1;i<=n;i++)
	{
		l[i]=1;r[i]=m;
	}
	while(true)
	{
		for(int i=1;i<=n;i++)
		{
			pr[i]=i;
			sz[i]=1;
		}
		bool any=false;
		for(int i=1;i<=qn;i++)
		{
			if(l[i]<r[i])
			{
				any=true;
				long long mid=(l[i]+r[i])/2;
				event[mid].push_back(i);
			}
		}
		if(!any) break;
		for(int mid=1;mid<=m;mid++)
		{
			uni(cau[mid].first,cau[mid].second);
			for(auto id:event[mid])
			{
				long long u=hoi[id].first,v=hoi[id].second;
				if(find(u)==find(v))
				{
					r[id]=mid;
				}
				else l[id]=mid+1;
			}
			event[mid].clear();
		}
	}
	for(int i=1;i<=qn;i++)
	{
		cout<<tt[l[i]-1].first<<"\n";
	}
	return 0;
}

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