Submission #714576

#	Time	Username	Problem	Language	Result	Execution time	Memory
714576		amirhoseinfar1385	Toll (BOI17_toll)	C++17	0 / 100	106 ms	5828 KiB

toll

#include<bits/stdc++.h>
using namespace std;
int k,n,m,o;
const int maxn=50000+10,sq=240;
vector<pair<int,int>>adj[maxn],revadj[maxn];
int dp[sq][5][5],inf=1e9+5;

void pre(){
	for(int i=0;i+sq<maxn;i+=sq){
		for(int j=0;j<k;j++){
			vector<int>allv(sq,inf);
			allv[j]=0;
			for(int h=i;h<i+sq;h++){
				for(auto x:revadj[h]){
					if(x.first>=i){
						allv[h-i]=min(allv[x.first-i]+x.second,allv[h-i]);
					}
				}
			}
			for(int h=0;h<k;h++){
				dp[i/sq][j][h]=allv[sq-(k-h)];
			}
		}
	}
}


void solve(int a,int b){
	vector<int>allv(sq+2,inf);
	if(b-a<=sq){
		allv[0]=0;
		for(int i=1;i<=b-a;i++){
			for(auto x:revadj[i+a]){
				if(x.first>=a){
					allv[i]=min(allv[i],allv[x.first-a]+x.second);
				}
			}
		}
		if(allv[b-a]==inf){
			cout<<-1<<"\n";
			return ;
		}
		cout<<allv[b-a]<<"\n";
		return ;
	}
	vector<int>revallv(sq+2,inf);
	int l=a-(a%sq);
	allv[a-l]=0;
	for(int i=a-l+1;i<sq;i++){
		for(auto x:revadj[l+i]){
			if(x.first>=l){
				allv[i]=min(allv[i],allv[x.first-l]+x.second);
			}
		}
	}
	l=b-(b%sq);
	revallv[b-l]=0;
	for(int i=b-l-1;i>=0;i--){
		for(auto x:adj[l+i]){
			if(x.first<=b){
				allv[i]=min(allv[i],allv[x.first-l]+x.second);
			}
		}
	}
	vector<int>now(k),last(k);
	for(int i=0;i<k;i++){
		now[i]=allv[sq-(k-i)];
		last[i]=revallv[i];
	}
	a-=(a%sq);
	a+=sq;
	while(a+sq<=b){
		//cout<<a<<endl;
		vector<int>fake(k,inf);
		for(int i=0;i<k;i++){
			for(auto x:adj[a-(k-i)]){
				if(x.first>=a){
					for(int j=0;j<k;j++){
						fake[j]=min(fake[j],dp[a/sq][x.first-a][j]+x.second+now[i]);
					}
				}
			}
		}
		swap(fake,now);
		fake.clear();
		a+=sq;
	//	cout<<a<<endl;
	}
	int res=inf;
	for(int i=0;i<k;i++){
		for(auto x:adj[a-(k-i)]){
			res=min(res,x.second+now[i]+last[x.first-a]);
		}
	}
	if(res==inf){
		cout<<-1<<"\n";
		return;
	}
	cout<<res<<"\n";
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);	
	cin>>k>>n>>m>>o;
	for(int i=0;i<m;i++){
		int a,b,w;
		cin>>a>>b>>w;
		adj[a].push_back(make_pair(b,w));
		revadj[b].push_back(make_pair(a,w));
	}
	pre();
	for(int i=0;i<o;i++){
		int a,b;
		cin>>a>>b;
		solve(a,b);
	}
}

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