Submission #1219749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219749		boclobanchat	Evacuation plan (IZhO18_plan)	C++20	100 / 100	440 ms	55352 KiB

plan

#include<bits/stdc++.h>
using namespace std;
struct query { int l,r,pos; };
const int MAXN=1e5+5;
const long long INF=1e18;
int dsu[MAXN],cnt[MAXN],pos[MAXN];
long long dp[MAXN],ans[MAXN];
bool ck[MAXN];
stack< pair<int,int> > st;
vector< pair<int,long long> > ds[MAXN];
priority_queue< pair<long long,int>,vector< pair<long long,int> >,greater< pair<long long,int> > > pq;
bool comp(int a,int b) { return dp[a]>dp[b]; }
int root(int i)
{
	if(!dsu[i]) return i;
	return root(dsu[i]);
}
void merge(int i,int j)
{
	if((i=root(i))==(j=root(j)))
	{
		st.push({-1,-1});
		return ;
	}
	if(cnt[i]<cnt[j]) swap(i,j);
	dsu[j]=i,cnt[i]+=cnt[j],st.push({i,j});
}
void rollback()
{
	pair<int,int> a=st.top();
	st.pop();
	if(a.first<0) return ;
	dsu[a.second]=0,cnt[a.first]-=cnt[a.second];
}
void update(int res)
{
	ck[res]=true;
	for(auto v:ds[res]) if(ck[v.first]) merge(res,v.first);
}
void rollback(int res)
{
	ck[res]=false;
	for(auto v:ds[res]) if(ck[v.first]) rollback();
}
void solve(int l,int r,vector<query> vq)
{
	if(l==r)
	{
		for(auto v:vq) ans[v.pos]=dp[pos[l]];
		update(pos[l]);
		return ;
	}
	int mid=(l+r)/2;
	vector<query> vl,vr;
	for(int i=l;i<=mid;i++) update(pos[i]);
	for(auto v:vq) if(ck[v.l]&&ck[v.r]&&root(v.l)==root(v.r)) vl.push_back(v);
	else vr.push_back(v);
	for(int i=mid;i>=l;i--) rollback(pos[i]);
	solve(l,mid,vl);
	solve(mid+1,r,vr);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,k,q;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cnt[i]=1,dp[i]=INF,pos[i]=i;
    for(int i=1;i<=m;i++)
    {
    	int l,r,v;
    	cin>>l>>r>>v;
    	ds[l].push_back({r,v}),ds[r].push_back({l,v});
	}
	cin>>k;
	while(k--)
	{
		int res;
		cin>>res;
		dp[res]=0,pq.push({0,res});
	}
	while(!pq.empty())
	{
		long long a=pq.top().first;
		int b=pq.top().second;
		pq.pop();
		if(dp[b]<a) continue;
		for(auto v:ds[b]) if(dp[v.first]>a+v.second) pq.push({dp[v.first]=a+v.second,v.first});
	}
	sort(pos+1,pos+n+1,comp);
	cin>>q;
	vector<query> vq;
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		vq.push_back({l,r,i});
	}
	solve(1,n,vq);
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

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