Submission #453764

#	Time	Username	Problem	Language	Result	Execution time	Memory
453764		naman1601	Toll (BOI17_toll)	C++17	100 / 100	530 ms	329940 KiB

toll

/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"
// #define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif

const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;


int k, n, m, o;
const int maxn = 50000 + 50;
const int maxjump = 17;
vector<vector<big>> dp[maxn][maxjump];


void combine(vector<vector<big>>& w, vector<vector<big>>& u, vector<vector<big>>& v) {

	fr(i, 0, k) {

		fr(j, 0, k) {

			fr(l, 0, k) {

				w[i][j] = min(w[i][j], u[i][l] + v[l][j]);
			}
		}
	}
}


void solve() {

	cin >> k >> n >> m >> o;

	fr(i, 0, maxn) {

		fr(j, 0, maxjump) {

			dp[i][j] = vector<vector<big>>(5, vector<big>(5, inf));
		}
	}

	fr(i, 0, m) {

		int u, v, w;
		cin >> u >> v >> w;
		dp[u / k][0][u % k][v % k] = w;
	}

	fr(jump, 1, maxjump) {

		fr(v, 0, n / k + 1) {

			if((v + (1 << (jump - 1))) > (n / k + 1)) break;

			combine(dp[v][jump], dp[v][jump - 1], dp[v + (1 << (jump - 1))][jump - 1]);
		}
	}

	fr(p, 0, o) {

		int u, v;
		cin >> u >> v;

		int x = u % k, y = v % k;
		u /= k;
		v /= k;

		if(u == v) {

			cout << -1 << nl;
			continue;
		}

		vector<vector<big>> a(5, vector<big>(5, inf));
		vector<vector<big>> b(5, vector<big>(5, inf));

		fr(i, 0, 5) {

			b[i][i] = 0;
		}

		revfr(jump, maxjump, 0) {

			if(u + (1 << jump) <= v) {

				combine(a, b, dp[u][jump]);

				fr(i, 0, 5) {

					fr(j, 0, 5) {

						b[i][j] = a[i][j];
						a[i][j] = inf;
					}
				}

				u += (1 << jump);

				if(u == v) break;
			}
		}

		big r = b[x][y];

		if(r < inf) {

			cout << r << nl;

		} else {

			cout << -1 << nl;
		}
	}
}


int main() {
	
	speed;

	int q = 1;
	// cin >> q;

	while(q-- > 0) {

		solve();
	}

	return 0;
}

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