Submission #1277993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277993		WH8	Toll (BOI17_toll)	C++20	0 / 100	669 ms	8004 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define pll pair<int, int>
#define int long long
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
const int blk=200;
int n,o,k,m;
vector<vector<int>> fw(50005, vector<int>(5, 1e12));
vector<int> dist(50005, 1e12);
vector<vector<pair<int,int>>> in(50005); 
void pass(int sl, int el){	
	for(int i=sl+1;i<=el;i++){ // reset.
		for(int j=0;j<k;j++){
			
			int cn=i*k+j;
			dist[cn]=1e12;
			for(auto [f, c]:in[cn]){
				dist[cn]=min(dist[cn], dist[f]+c);
			}
		}
	}
}

signed main(){
	//~ cin.tie(0);
	cin>>k>>n>>m>>o;
	for(int i=0;i<m;i++){
		int a,b,t;cin>>a>>b>>t;
		in[b].pb({a, t});
	}
	for(int i=0;i<n;i++){
		// calc distances after forwarding 200 . 
		// reset dist of current layer.
		int sl=i/k;
		for(int j=0;j<k;j++){
			int cn=sl*k+j;
			dist[cn]=1e12;
		}
		dist[i]=0;
		pass(sl, sl+blk);
		int el=sl+blk;
		for(int j=0;j<k;j++){
			int cn=el*k+j;
			fw[i][j]=dist[cn];
		}
	}
	
	while(o--){
		int a,b;cin>>a>>b;
		vector<int> layer(k, 1e12); layer[a%k]=0;
		int cl=a/k, el=b/k;
		while(el - el >= blk){
			vector<int> nxt(k, 1e12);
			for(int i=0;i<k;i++){
				int cn=cl*k+i;
				for(int j=0;j<k;j++){
					nxt[j]=min(nxt[j], layer[i]+fw[cn][j]);
				}
			}
			swap(layer, nxt);
			cl+=blk;
		}
		for(int i=0;i<k;i++){
			dist[cl*k+i]=layer[i];
		}
		pass(cl, el);
		if(dist[b] >= 1e12)cout<<-1<<"\n";
		else cout<<dist[b]<<"\n";
	}
}
		
	

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