oj.uz

Submission #453764

# Submission time Handle Problem Language Result Execution time Memory
453764 2021-08-04T17:33:08 Z naman1601 Toll (BOI17_toll) C++17
100 / 100
 530 ms 329940 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 + 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 326652 KB Output is correct
2 Correct 446 ms 326540 KB Output is correct
3 Correct 366 ms 326644 KB Output is correct
4 Correct 375 ms 326568 KB Output is correct
5 Correct 401 ms 326680 KB Output is correct
6 Correct 401 ms 326596 KB Output is correct
7 Correct 366 ms 326672 KB Output is correct
8 Correct 489 ms 327592 KB Output is correct
9 Correct 491 ms 327448 KB Output is correct
10 Correct 468 ms 326832 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 326644 KB Output is correct
2 Correct 361 ms 326652 KB Output is correct
3 Correct 415 ms 326576 KB Output is correct
4 Correct 367 ms 326596 KB Output is correct
5 Correct 373 ms 326580 KB Output is correct
6 Correct 366 ms 326652 KB Output is correct
7 Correct 376 ms 326716 KB Output is correct
8 Correct 366 ms 326736 KB Output is correct
9 Correct 484 ms 327512 KB Output is correct
10 Correct 485 ms 329072 KB Output is correct
11 Correct 486 ms 328388 KB Output is correct
12 Correct 465 ms 327872 KB Output is correct
13 Correct 452 ms 329044 KB Output is correct
14 Correct 439 ms 328164 KB Output is correct
15 Correct 424 ms 327840 KB Output is correct
16 Correct 423 ms 327876 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 326628 KB Output is correct
2 Correct 362 ms 326592 KB Output is correct
3 Correct 358 ms 326560 KB Output is correct
4 Correct 363 ms 326652 KB Output is correct
5 Correct 367 ms 326584 KB Output is correct
6 Correct 382 ms 326668 KB Output is correct
7 Correct 365 ms 326684 KB Output is correct
8 Correct 372 ms 326980 KB Output is correct
9 Correct 367 ms 326700 KB Output is correct
10 Correct 461 ms 327572 KB Output is correct
11 Correct 465 ms 328172 KB Output is correct
12 Correct 478 ms 328728 KB Output is correct
13 Correct 467 ms 329004 KB Output is correct
14 Correct 461 ms 328464 KB Output is correct
15 Correct 420 ms 327852 KB Output is correct
16 Correct 401 ms 327708 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 326628 KB Output is correct
2 Correct 362 ms 326592 KB Output is correct
3 Correct 358 ms 326560 KB Output is correct
4 Correct 363 ms 326652 KB Output is correct
5 Correct 367 ms 326584 KB Output is correct
6 Correct 382 ms 326668 KB Output is correct
7 Correct 365 ms 326684 KB Output is correct
8 Correct 372 ms 326980 KB Output is correct
9 Correct 367 ms 326700 KB Output is correct
10 Correct 461 ms 327572 KB Output is correct
11 Correct 465 ms 328172 KB Output is correct
12 Correct 478 ms 328728 KB Output is correct
13 Correct 467 ms 329004 KB Output is correct
14 Correct 461 ms 328464 KB Output is correct
15 Correct 420 ms 327852 KB Output is correct
16 Correct 401 ms 327708 KB Output is correct
17 Correct 505 ms 328328 KB Output is correct
18 Correct 354 ms 326648 KB Output is correct
19 Correct 360 ms 326736 KB Output is correct
20 Correct 364 ms 326648 KB Output is correct
21 Correct 365 ms 326532 KB Output is correct
22 Correct 362 ms 326652 KB Output is correct
23 Correct 364 ms 326760 KB Output is correct
24 Correct 362 ms 326644 KB Output is correct
25 Correct 384 ms 326724 KB Output is correct
26 Correct 361 ms 326656 KB Output is correct
27 Correct 477 ms 327488 KB Output is correct
28 Correct 477 ms 328760 KB Output is correct
29 Correct 494 ms 329184 KB Output is correct
30 Correct 474 ms 328468 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 326652 KB Output is correct
2 Correct 446 ms 326540 KB Output is correct
3 Correct 366 ms 326644 KB Output is correct
4 Correct 375 ms 326568 KB Output is correct
5 Correct 401 ms 326680 KB Output is correct
6 Correct 401 ms 326596 KB Output is correct
7 Correct 366 ms 326672 KB Output is correct
8 Correct 489 ms 327592 KB Output is correct
9 Correct 491 ms 327448 KB Output is correct
10 Correct 468 ms 326832 KB Output is correct
11 Correct 525 ms 326644 KB Output is correct
12 Correct 361 ms 326652 KB Output is correct
13 Correct 415 ms 326576 KB Output is correct
14 Correct 367 ms 326596 KB Output is correct
15 Correct 373 ms 326580 KB Output is correct
16 Correct 366 ms 326652 KB Output is correct
17 Correct 376 ms 326716 KB Output is correct
18 Correct 366 ms 326736 KB Output is correct
19 Correct 484 ms 327512 KB Output is correct
20 Correct 485 ms 329072 KB Output is correct
21 Correct 486 ms 328388 KB Output is correct
22 Correct 465 ms 327872 KB Output is correct
23 Correct 452 ms 329044 KB Output is correct
24 Correct 439 ms 328164 KB Output is correct
25 Correct 424 ms 327840 KB Output is correct
26 Correct 423 ms 327876 KB Output is correct
27 Correct 365 ms 326628 KB Output is correct
28 Correct 362 ms 326592 KB Output is correct
29 Correct 358 ms 326560 KB Output is correct
30 Correct 363 ms 326652 KB Output is correct
31 Correct 367 ms 326584 KB Output is correct
32 Correct 382 ms 326668 KB Output is correct
33 Correct 365 ms 326684 KB Output is correct
34 Correct 372 ms 326980 KB Output is correct
35 Correct 367 ms 326700 KB Output is correct
36 Correct 461 ms 327572 KB Output is correct
37 Correct 465 ms 328172 KB Output is correct
38 Correct 478 ms 328728 KB Output is correct
39 Correct 467 ms 329004 KB Output is correct
40 Correct 461 ms 328464 KB Output is correct
41 Correct 420 ms 327852 KB Output is correct
42 Correct 401 ms 327708 KB Output is correct
43 Correct 505 ms 328328 KB Output is correct
44 Correct 354 ms 326648 KB Output is correct
45 Correct 360 ms 326736 KB Output is correct
46 Correct 364 ms 326648 KB Output is correct
47 Correct 365 ms 326532 KB Output is correct
48 Correct 362 ms 326652 KB Output is correct
49 Correct 364 ms 326760 KB Output is correct
50 Correct 362 ms 326644 KB Output is correct
51 Correct 384 ms 326724 KB Output is correct
52 Correct 361 ms 326656 KB Output is correct
53 Correct 477 ms 327488 KB Output is correct
54 Correct 477 ms 328760 KB Output is correct
55 Correct 494 ms 329184 KB Output is correct
56 Correct 474 ms 328468 KB Output is correct
57 Correct 530 ms 329940 KB Output is correct
58 Correct 497 ms 327592 KB Output is correct
59 Correct 529 ms 328640 KB Output is correct