Submission #702741

#	Time	Username	Problem	Language	Result	Execution time	Memory
702741		Zian_Jacobson	Toll (BOI17_toll)	C++17	100 / 100	316 ms	51752 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define cIO ios_base::sync_with_stdio(0);cin.tie(0)
#define fileIO(x) ifstream fin(string(x)+".in"); ofstream fout(string(x)+".out")
#define cont(container, object) (container.find(object)!=container.end())
#define sz(x) (int) (x).size()
#define ll long long
#define v vector
const int max_log = 17;
const int INF = INT_MAX / 3;
v<v<v<int>>> jmp;
int K, N, M, O;
//if WA use ll
int main()
{
	//everything 0-indexed
	fileIO("toll");
	
	cin >> K >> N >> M >> O;
	jmp= v<v<v<int>>>(N+6, v<v<int>>(max_log, v<int>(K, INF)));//[node][2^depth]=vector of costs
	for (int i = 0; i <= M - 1; i++)
	{
		int a, b, t; cin >> a >> b >> t;
		jmp[a][0][b%K] = t;
	}
	//debug
	/*for (int i = 0; i <= N - 1; i++)
	{
		cout << i << ": ";
		for (int j = 0; j <= K - 1; j++)
		{
			if (jmp[i][0][j] == INF) cout << "NUL ";
			else cout << jmp[i][0][j] << " ";
		}
		cout << "\n";
	}*/
	for (int dep=1; dep<=max_log; dep++)
		for (int i = 0; i <= N - 1; i++)
		{
			int mid_start = (i / K + (1<<(dep-1))) * K, mid_end = mid_start + 4;
			int res_start= (i / K + (1 << (dep))) * K, res_end = res_start + 4;
			if (res_start >= N) continue;
			for (int x = 0; x <= K - 1; x++)//x is the index of the middle
			{
				for (int y = 0; y <= K - 1; y++)//y is the index of the result
				{
					jmp[i][dep][y] = min(jmp[i][dep][y],
						jmp[i][dep - 1][x] + jmp[mid_start + x][dep - 1][y]);
				}
				//jmp should not be above INF or something is wrong
			}
		}
	//answer queries
	for (int q = 0; q <= O - 1; q++)
	{
		int a, b; cin >> a >> b;
		int tot_jumps = (int)(b / K) - a / K;
		if (tot_jumps == 0)
		{
			cout << "-1\n";
			continue;
		}
		int b_pos = b % K;
		int cur_pos = (int)(a / K)*K;
		v<int> cur_arr(K, INF); cur_arr[a % K] = 0;
		for (int i = 0; i <= max_log; i++)
		{
			if (tot_jumps & (1 << i))//we should jump i
			{
				v<int> new_arr(K, INF);
				for (int x = 0; x <= K - 1; x++)
					for (int y = 0; y <= K - 1; y++)
						new_arr[y] = min(new_arr[y], jmp[cur_pos + x][i][y] + cur_arr[x]);
				cur_arr = new_arr;
				cur_pos += K*(1 << i);
			}
		}
		if (cur_arr[b_pos] == INF) cout << "-1\n";
		else cout << cur_arr[b_pos] << "\n";
	}
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:40:48: warning: unused variable 'mid_end' [-Wunused-variable]
   40 |    int mid_start = (i / K + (1<<(dep-1))) * K, mid_end = mid_start + 4;
      |                                                ^~~~~~~
toll.cpp:41:47: warning: unused variable 'res_end' [-Wunused-variable]
   41 |    int res_start= (i / K + (1 << (dep))) * K, res_end = res_start + 4;
      |                                               ^~~~~~~

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