Submission #847860

#	Time	Username	Problem	Language	Result	Execution time	Memory
847860		_Avocado_	Toll (BOI17_toll)	C++14	100 / 100	179 ms	42772 KiB

toll

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

const int INF = 1e10;
const int LG = 20;
const int MAX_N = 5e4+4;
const int MAX_K = 5;

int up[MAX_N][LG][MAX_K];

int dijkstra(int s, int e, int K, auto&graph){
	vector<int>dist(LG*K, -1);
	
	priority_queue<pair<int, int>>pq;
	pq.push({0, s});
	
	while(pq.size()){
		auto [d, u] = pq.top();
		pq.pop();
		
		if(dist[u] != -1) continue;
		
		d = -d;
		dist[u] = d;
		
		for(auto [v, w]: graph[u]){
			pq.push({-(w+d), v});
		}
	}
	
	return dist[e];
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	
	int K, n, m, q; cin>>K>>n>>m>>q;
	
	for(int i = 0; i<MAX_N; ++i){
		for(int j = 0; j<LG; ++j){
			for(int k = 0; k<MAX_K; ++k) up[i][j][k] = INF;
		}
	}
	
	for(int i = 0; i<m; ++i){
		int a, b, c; cin>>a>>b>>c;
		up[a][0][b%K] = c;
	}
	
	for(int jumps = 1; jumps<LG; ++jumps){
		for(int i = 0; i<n; ++i){
			for(int k = 0; k<K; ++k){
				for(int middle = 0; middle < K; ++middle){
					int mid_node = i/K*K + ((1<<(jumps-1))*K) + middle;
					if(mid_node > n) break;
					up[i][jumps][k] = min(up[i][jumps][k], up[i][jumps-1][middle] + up[mid_node][jumps-1][k]);
				}
			}
		}
	}
	/*
	for(int i = 0; i<5; ++i){
		for(int k = 0; k<K; ++k) cout<<up[0][i][k]<<" ";
		cout<<endl;
	}
	cout<<endl;
	
	for(int i = 0; i<5; ++i){
		for(int k = 0; k<K; ++k) cout<<up[2][i][k]<<" ";
		cout<<endl;
	}
	cout<<endl;
	
	for(int i = 0; i<5; ++i){
		for(int k = 0; k<K; ++k) cout<<up[3][i][k]<<" ";
		cout<<endl;
	}
	cout<<endl;
	*/
	
	
	for(int i = 0; i<q; ++i){
		int a, b; cin>>a>>b;
		
		vector<vector<pair<int, int>>>graph(LG*K);
		
		int cnt = 0;
		int group = a/K*K;
		int cur_jumps = (b/K) - (a/K);
		
		if(!cur_jumps){
			cout<<-1<<'\n';
			continue;
		}
		
		int start = a%K;
		int maxi = 0;
		
		for(int j = LG-1; j>=0; --j){
			if(cur_jumps - (1<<j) >= 0){
				cur_jumps -= (1<<j);
				for(int k1 = 0; k1<K; ++k1){
					for(int k2 = 0; k2<K; ++k2){
						if(group + k1 > n) break;
						
						int node1 = cnt + k1;
						int node2 = cnt + K + k2;
						
						maxi = node2;
						
						graph[node1].push_back({node2, up[group+k1][j][k2]});
					}
				}
				cnt += K;
				group += (1<<j)*K;
			}
		}
		/*
		for(int j = 0; j<10; ++j){
			cout<<"j "<<j<<endl;
			for(auto u: graph[j]) cout<<u.first<<" "<<u.second<<endl;
			cout<<endl;
		}
		*/
		
		int end = maxi-K+1+(b%K);
		
		//cout<<"end "<<end<<endl;
		
		int ans = dijkstra(start, end, K, graph);
		
		if(ans >= INF) cout<<-1<<'\n';
		else cout<<ans<<'\n';
	}
					
	//cout<<'\n';
}

Compilation message (stderr)

toll.cpp:12:35: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | int dijkstra(int s, int e, int K, auto&graph){
      |                                   ^~~~
toll.cpp: In function 'int64_t dijkstra(int64_t, int64_t, int64_t, auto:1&)':
toll.cpp:19:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |   auto [d, u] = pq.top();
      |        ^
toll.cpp:27:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |   for(auto [v, w]: graph[u]){
      |            ^

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