Submission #453751

# Submission time Handle Problem Language Result Execution time Memory
453751 2021-08-04T16:57:47 Z naman1601 Toll (BOI17_toll) C++17
0 / 100
765 ms 524288 KB
/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#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 + 5;
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) / k) {

			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 % 5, y = v % 5;
		u /= 5;
		v /= 5;

		if(u == v) {

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

		vector<vector<big>> a(5, vector<big>(5, inf));
		vector<vector<big>> b(5, vector<big>(5, 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);
			}
		}

		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;
}
# Verdict Execution time Memory Grader output
1 Runtime error 706 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 765 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 326256 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 326256 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 706 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -