Submission #393471

#	Time	Username	Problem	Language	Result	Execution time	Memory
393471		Nordway	Toll (BOI17_toll)	C++17	100 / 100	158 ms	13248 KiB

toll

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sz(v) v.size()
#define up_b upper_bound
#define low_b lower_bound
#define all(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef long double ld;

const int N=5e4+11;
const ll mod=1e9+7;
const int inf=1e9;

int k,n,m,o;

int lef[5][N],rig[5][N];
vector<pair<int,int>>g[N][2];
int ans[N];
int A[N],B[N];

void go(int l,int r,vector<int>orders){
	if(l==r){
		for(int i:orders){
			ans[i]=inf;
		}
		return ;
	}
	int mid=(l+r)/2;
	for(int x=0;x<k;x++){
		for(int i=l*k;i<(r+1)*k;i++){
			lef[x][i]=inf;
			rig[x][i]=inf;
		}
		lef[x][mid*k+x]=0;
		rig[x][mid*k+x]=0;
		for(int i=(mid+1)*k;i<(r+1)*k;i++){
			for(pair<int,int>p:g[i][1]){
				rig[x][i]=min(rig[x][i],rig[x][p.x]+p.y);
			}
		}
		for(int i=mid*k-1;i>=l*k;i--){
			for(pair<int,int>p:g[i][0]){
				lef[x][i]=min(lef[x][i],lef[x][p.x]+p.y);
			}
		}
	}
	vector<int>todo[2];
	for(int i:orders){
		int a=A[i],b=B[i];
		if(a/k<=mid&&mid<b/k){
			ans[i]=inf;
			for(int x=0;x<k;x++){
				ans[i]=min(ans[i],lef[x][a]+rig[x][b]);
			}
			continue;
		}
		todo[a/k>mid].pb(i);
	}
	go(l,mid,todo[0]);
	go(mid+1,r,todo[1]);
}

void solve() {
	cin>>k>>n>>m>>o;
	for(int i=1;i<=m;i++){
		int a,b,t;
		cin>>a>>b>>t;
		g[a][0].pb(mp(b,t));
		g[b][1].pb(mp(a,t));
	}
	vector<int>orders;
	for(int i=0;i<o;i++){
		cin>>A[i]>>B[i];
		orders.pb(i);
	}
	go(0,(n-1)/k,orders);
	for(int i=0;i<o;i++){
		if(ans[i]==inf)ans[i]=-1;
		cout<<ans[i]<<"\n";
	}

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T=1;
	//cin>>T;
	while(T--){
		solve();
		cout<<"\n";
	}
}

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