Submission #338628

#	Time	Username	Problem	Language	Result	Execution time	Memory
338628		Kevin_Zhang_TW	Toll (BOI17_toll)	C++17	100 / 100	128 ms	82668 KiB

toll

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
template<class T>
bool chmax(T &val, T nv) { return val < nv ? (val = nv, true) : false; }
template<class T>
bool chmin(T &val, T nv) { return nv < val ? (val = nv, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T1, class ...T2>
void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 50010, inf = 1e9, MAX_K = 5, MAX_L = 16;

int k, n, m, q;
#pragma GCC optimize("Ofast")
int dp[MAX_L][MAX_N][MAX_K][MAX_K];
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> k >> n >> m >> q;
	for (int i = 0;i < MAX_L;++i) for (int j = 0;j < n;++j) for (int l = 0;l < k;++l) for (int m = 0;m < k;++m) 
		dp[i][j][l][m] = inf;

	for (int a, b, t, i = 0;i < m;++i) {
		cin >> a >> b >> t;
		dp[0][a / k][a % k][b % k] = t;
	}
	for (int d = 1;1 << d <= n;++d) {
		for (int i = 0;i < n / k;++i)
			for (int j = 0;j < k;++j) for (int l = 0;l < k;++l)
				for (int m = 0;m < k;++m)
					chmin(dp[d][i][j][m], dp[d-1][i][j][l] + dp[d-1][i + (1<<(d-1))][l][m]);
	}
	auto qry = [&](int a, int b) {
		if (a / k == b / k) return -1;
		int dis = b / k - a / k;
		int *mat = new int[k], *tmp = new int[k];
		for (int i = 0;i < k;++i) mat[i] = inf;

		mat[a % k] = 0;

		for (int d = 0;1 << d <= dis;++d) if (dis >> d & 1) {
			DE(d);
			fill(tmp, tmp + k, inf);
			for (int i = 0;i < k;++i) for (int j = 0;j < k;++j) {
				chmin(tmp[j], mat[i] + dp[d][a / k][i][j]);
			}
			a += (1 << d) * k;
			swap(tmp, mat);
		}
		return mat[b % k] == inf ? -1 : mat[b % k];
	};
	while (q--) {
		int a, b;
		cin >> a >> b;
		cout << qry(a, b) << '\n';
	}
}

Compilation message (stderr)

toll.cpp: In lambda function:
toll.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
toll.cpp:56:4: note: in expansion of macro 'DE'
   56 |    DE(d);
      |    ^~

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