oj.uz

Submission #567568

# Submission time Handle Problem Language Result Execution time Memory
567568 2022-05-23T17:39:01 Z _karan_gandhi Toll (BOI17_toll) C++17
7 / 100
 144 ms 198812 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

void solve() {
	ll int k, n, m, o; cin >> k >> n >> m >> o;

	// const ll int inf = 1e16;
	const ll int LOG = 20;
	ll int dp[n / k][LOG][5][5];
	memset(dp, 1, sizeof dp);

	// dp[i][i + 2 ^ k][x][y];
	vector<vector<pair<ll int, ll int>>> adj(n);

	for (ll int i = 0; i < m; i++) {
		ll int a, b; cin >> a >> b;
		ll int c; cin >> c;

		adj[a].emplace_back(b, c);
	}

	for (ll int i = 0; i < n; i++) {
		for (auto [v, wt] : adj[i]) {
			dp[i / k][0][i % k][v % k] = wt;
		}
	}

	auto combine = [&](ll int target[5][5], ll int a[5][5], ll int b[5][5]) {
		for (ll int i = 0; i < k; i++) {
			for (ll int j = 0; j < k; j++) {
				for (ll int l = 0; l < k; l++) {
					target[i][j] = min(target[i][j], a[i][l] + b[l][j]);
				}
			}
		}
	};

	for (ll int i = 1; i < LOG; i++) {
		for (ll int j = 0; j < n / k; j++) {
			if (j + (1 << (i - 1)) >= n / k) continue;
			combine(dp[j][i], dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);
		// 	for (ll int ii = 0; ii < k; ii++) {
		// 		for (ll int jj = 0; jj < k; jj++) {
		// 			cout << pl(i) << pl(j) << pl(ii) << pl(jj) << pl(dp[j][i][ii][jj]) << endl;
		// 		}
		// 	}
		}
	}

	auto query = [&](ll int start, ll int levels, ll int en) {
		// cout << pl(start) << pl(en) << endl;
		// ll int _start = start;
		ll int res[5][5];
		ll int level = start / k;
		memset(res, 1, sizeof res);
		for (ll int i = 0; i < k; i++) res[i][i] = 0;
		// res[start % k][start % k] = 0;
		ll int pow = LOG;

		while (levels > 0) {
			while (levels < (1 << pow)) pow--;

			ll int new_res[5][5];
			memset(new_res, 1, sizeof new_res);

			combine(new_res, res, dp[level][pow]);
			memcpy(res, new_res, sizeof res);

			level += (1 << pow);
			levels -= (1 << pow);

			// cout << pl(levels) << endl;
			// for (ll int ii = 0; ii < k; ii++) {
			// 	for (ll int jj = 0; jj < k; jj++) {
			// 		cout << pl(ii) << pl(jj) << pl(new_res[ii][jj]) << endl;
			// 	}
			// }
		}

		// for (ll int ii = 0; ii < k; ii++) {
		// 	for (ll int jj = 0; jj < k; jj++) {
		// 		cout << pl(ii) << pl(jj) << pl(res[ii][jj]) << endl;
		// 	}
		// }
		// cout << pl(res[0][2]) << endl;
		// cout << pl(start % k) << pl(en % k) << endl;
		// cout << pl(start) << endl;
		return res[start % k][en % k];
	};

	// cout << pl(dp[0][1][0][2]) << endl;
	// cout << pl(dp[0][1][4][2]) << endl;

	while (o--) {
		ll int a, b; cin >> a >> b;
		// cout << pl(a) << pl(b) << endl;
		ll int levels = abs(a / k - b / k);
		// cout << pl(levels) << endl;
		if (levels == 0) {
			cout << -1 << endl;
		}
		ll int res = query(a, levels, b);
		// cout << pl(res) << endl;
		if (res > 1e16) {
			cout << -1 << endl;
		} else {
			cout << res << endl;
		}
	}
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll int T = 1;
	// cin >> T;
	while (T--)
		solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 198812 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 4256 KB Output is correct
6 Correct 4 ms 4180 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 144 ms 198720 KB Output is correct
9 Correct 130 ms 198600 KB Output is correct
10 Correct 126 ms 197120 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 101856 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 198812 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 4256 KB Output is correct
6 Correct 4 ms 4180 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 144 ms 198720 KB Output is correct
9 Correct 130 ms 198600 KB Output is correct
10 Correct 126 ms 197120 KB Output is correct
11 Correct 115 ms 101856 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -