oj.uz

Submission #847852

# Submission time Handle Problem Language Result Execution time Memory
847852 2023-09-10T15:49:55 Z _Avocado_ Toll (BOI17_toll) C++14
7 / 100
 66 ms 40516 KB 
#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){
					if(i + middle + ((1<<(jumps-1))*K) > n) break;
					up[i][jumps][k] = min(up[i][jumps][k], up[i][jumps-1][middle] + up[i + middle + ((1<<(jumps-1))*K)][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);
		
		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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 39516 KB Output is correct
2 Correct 6 ms 39512 KB Output is correct
3 Correct 7 ms 39516 KB Output is correct
4 Correct 6 ms 39516 KB Output is correct
5 Correct 8 ms 39620 KB Output is correct
6 Correct 7 ms 39516 KB Output is correct
7 Correct 7 ms 39516 KB Output is correct
8 Correct 35 ms 40516 KB Output is correct
9 Correct 34 ms 40284 KB Output is correct
10 Correct 23 ms 39516 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 39516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39516 KB Output is correct
2 Incorrect 6 ms 39516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39516 KB Output is correct
2 Incorrect 6 ms 39516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 39516 KB Output is correct
2 Correct 6 ms 39512 KB Output is correct
3 Correct 7 ms 39516 KB Output is correct
4 Correct 6 ms 39516 KB Output is correct
5 Correct 8 ms 39620 KB Output is correct
6 Correct 7 ms 39516 KB Output is correct
7 Correct 7 ms 39516 KB Output is correct
8 Correct 35 ms 40516 KB Output is correct
9 Correct 34 ms 40284 KB Output is correct
10 Correct 23 ms 39516 KB Output is correct
11 Incorrect 66 ms 39516 KB Output isn't correct
12 Halted 0 ms 0 KB -