제출 #1220084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220084		boclobanchat	Toll (BOI17_toll)	C++20	7 / 100	57 ms	6668 KiB

toll

#include<bits/stdc++.h>
using namespace std;
struct query { int l,r,pos; };
const int MAXN=5e4+5;
const int INF=1e9;
vector< pair<int,int> > ds[MAXN],sd[MAXN];
int ans[MAXN],dpl[MAXN],dpr[MAXN];
void dnc(int l,int r,int k,vector<query> vq)
{
	if(l==r)
	{
		for(auto v:vq) ans[v.pos]=-1;
		return ;
	}
	int mid=(l+r)/2;
	priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > pq,qp;
	for(int i=l*k;i<(r+1)*k;i++) dpl[i]=dpr[i]=INF;
	for(int i=mid*k;i<(mid+1)*k;i++) dpl[i]=dpr[i]=0,qp.push({0,i}),pq.push({0,i});
	while(!pq.empty())
	{
		int a=pq.top().first,b=pq.top().second;
		pq.pop();
		if(dpr[b]<a) continue;
		for(auto v:ds[b]) if(dpr[v.first]>a+v.second) pq.push({dpr[v.first]=a+v.second,v.first});
	}
	while(!qp.empty())
	{
		int a=qp.top().first,b=qp.top().second;
		qp.pop();
		if(dpl[b]<a) continue;
		for(auto v:sd[b]) if(dpl[v.first]>a+v.second) qp.push({dpl[v.first]=a+v.second,v.first});
	}
	vector<query> vl,vr;
	for(auto v:vq) if((mid+1)*k<=v.l) vr.push_back(v);
	else if(v.r<(mid+1)*k) vl.push_back(v);
	else if(dpl[v.l]+dpr[v.r]>=INF) ans[v.pos]=-1;
	else ans[v.pos]=dpl[v.l]+dpr[v.r];
	dnc(l,mid,k,vl);
	dnc(mid+1,r,k,vr);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k,n,m,q;
    cin>>k>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
    	int l,r,v;
    	cin>>l>>r>>v;
    	ds[l].push_back({r,v}),sd[r].push_back({l,v});
	}
	vector<query> vq;
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		vq.push_back({l,r,i});
	}
	dnc(0,(n-1)/k,k,vq);
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44