답안 #468935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468935	2021-08-30T08:38:21 Z	wind_reaper	Toll (BOI17_toll)	C++17	100 / 100	163 ms	81888 KB

toll

#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************

const int MXN = 50001;
const int LOG = 16;

//***************** GLOBAL VARIABLES *****************

int dp[MXN][LOG][5][5];

//***************** AUXILIARY STRUCTS *****************



//***************** MAIN BODY *****************

void solve(){
	int K, N, M, O;
	cin >> K >> N >> M >> O;
	
	int B = N / K;

	memset(dp, 0x3f, sizeof dp);

	for(int i = 0; i < M; i++){
		int u, v, t;
		cin >> u >> v >> t;
		dp[u / K][0][u % K][v % K] = t;
	}

	for(int j = 1; j < LOG; j++){
		for(int i = 0; i <= B; i++){
			for(int f = 0; f < K; f++)
				for(int t = 0; t < K; t++){
					if(i + (1 << j) > B) continue;
					for(int m = 0; m < K; m++)
						dp[i][j][f][t] = min(dp[i][j][f][t], dp[i][j-1][f][m] + dp[i + (1 << (j - 1))][j-1][m][t]);
				}
		}
	}

	for(int _ = 0; _ < O; _++){
		int u, v;
		cin >> u >> v;
		int x = u / K, y = v / K;

		int res[K];
		memset(res, 0x3f, sizeof res);
		res[u % K] = 0;

		for(int j = LOG - 1; j >= 0; --j){
			if(x + (1 << j) <= y){
				int cur[K];
				memset(cur, 0x3f, sizeof cur);

				for(int t = 0; t < K; t++)
					for(int f = 0; f < K; f++)
						cur[t] = min(cur[t], res[f] + dp[x][j][f][t]);

				for(int i = 0; i < K; i++)
					res[i] = cur[i];

				x += (1 << j);
			}
		}

		cout << (res[v % K] == 1061109567 ? -1 : res[v % K]) << '\n';
	}
}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic

4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	79556 KB	Output is correct
2	Correct	40 ms	78524 KB	Output is correct
3	Correct	41 ms	78500 KB	Output is correct
4	Correct	40 ms	78536 KB	Output is correct
5	Correct	42 ms	78532 KB	Output is correct
6	Correct	42 ms	78496 KB	Output is correct
7	Correct	41 ms	78536 KB	Output is correct
8	Correct	92 ms	79428 KB	Output is correct
9	Correct	93 ms	79472 KB	Output is correct
10	Correct	71 ms	78624 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	124 ms	80324 KB	Output is correct
2	Correct	40 ms	78524 KB	Output is correct
3	Correct	40 ms	78484 KB	Output is correct
4	Correct	40 ms	78540 KB	Output is correct
5	Correct	41 ms	78552 KB	Output is correct
6	Correct	40 ms	78560 KB	Output is correct
7	Correct	45 ms	78660 KB	Output is correct
8	Correct	45 ms	78664 KB	Output is correct
9	Correct	88 ms	79480 KB	Output is correct
10	Correct	124 ms	80864 KB	Output is correct
11	Correct	122 ms	80300 KB	Output is correct
12	Correct	102 ms	79856 KB	Output is correct
13	Correct	114 ms	80964 KB	Output is correct
14	Correct	85 ms	79936 KB	Output is correct
15	Correct	88 ms	79712 KB	Output is correct
16	Correct	84 ms	79816 KB	Output is correct

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	78644 KB	Output is correct
2	Correct	41 ms	78556 KB	Output is correct
3	Correct	40 ms	78524 KB	Output is correct
4	Correct	41 ms	78480 KB	Output is correct
5	Correct	40 ms	78528 KB	Output is correct
6	Correct	43 ms	78476 KB	Output is correct
7	Correct	41 ms	78504 KB	Output is correct
8	Correct	44 ms	78532 KB	Output is correct
9	Correct	41 ms	78584 KB	Output is correct
10	Correct	80 ms	79284 KB	Output is correct
11	Correct	108 ms	80096 KB	Output is correct
12	Correct	125 ms	80652 KB	Output is correct
13	Correct	127 ms	80940 KB	Output is correct
14	Correct	111 ms	80384 KB	Output is correct
15	Correct	84 ms	79760 KB	Output is correct
16	Correct	83 ms	79716 KB	Output is correct

Subtask #4
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	78644 KB	Output is correct
2	Correct	41 ms	78556 KB	Output is correct
3	Correct	40 ms	78524 KB	Output is correct
4	Correct	41 ms	78480 KB	Output is correct
5	Correct	40 ms	78528 KB	Output is correct
6	Correct	43 ms	78476 KB	Output is correct
7	Correct	41 ms	78504 KB	Output is correct
8	Correct	44 ms	78532 KB	Output is correct
9	Correct	41 ms	78584 KB	Output is correct
10	Correct	80 ms	79284 KB	Output is correct
11	Correct	108 ms	80096 KB	Output is correct
12	Correct	125 ms	80652 KB	Output is correct
13	Correct	127 ms	80940 KB	Output is correct
14	Correct	111 ms	80384 KB	Output is correct
15	Correct	84 ms	79760 KB	Output is correct
16	Correct	83 ms	79716 KB	Output is correct
17	Correct	118 ms	80136 KB	Output is correct
18	Correct	41 ms	78480 KB	Output is correct
19	Correct	40 ms	78496 KB	Output is correct
20	Correct	43 ms	78532 KB	Output is correct
21	Correct	41 ms	78500 KB	Output is correct
22	Correct	39 ms	78484 KB	Output is correct
23	Correct	43 ms	78532 KB	Output is correct
24	Correct	42 ms	78532 KB	Output is correct
25	Correct	43 ms	78692 KB	Output is correct
26	Correct	46 ms	78632 KB	Output is correct
27	Correct	83 ms	79324 KB	Output is correct
28	Correct	128 ms	80756 KB	Output is correct
29	Correct	137 ms	80984 KB	Output is correct
30	Correct	119 ms	80580 KB	Output is correct

Subtask #5
44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	79556 KB	Output is correct
2	Correct	40 ms	78524 KB	Output is correct
3	Correct	41 ms	78500 KB	Output is correct
4	Correct	40 ms	78536 KB	Output is correct
5	Correct	42 ms	78532 KB	Output is correct
6	Correct	42 ms	78496 KB	Output is correct
7	Correct	41 ms	78536 KB	Output is correct
8	Correct	92 ms	79428 KB	Output is correct
9	Correct	93 ms	79472 KB	Output is correct
10	Correct	71 ms	78624 KB	Output is correct
11	Correct	124 ms	80324 KB	Output is correct
12	Correct	40 ms	78524 KB	Output is correct
13	Correct	40 ms	78484 KB	Output is correct
14	Correct	40 ms	78540 KB	Output is correct
15	Correct	41 ms	78552 KB	Output is correct
16	Correct	40 ms	78560 KB	Output is correct
17	Correct	45 ms	78660 KB	Output is correct
18	Correct	45 ms	78664 KB	Output is correct
19	Correct	88 ms	79480 KB	Output is correct
20	Correct	124 ms	80864 KB	Output is correct
21	Correct	122 ms	80300 KB	Output is correct
22	Correct	102 ms	79856 KB	Output is correct
23	Correct	114 ms	80964 KB	Output is correct
24	Correct	85 ms	79936 KB	Output is correct
25	Correct	88 ms	79712 KB	Output is correct
26	Correct	84 ms	79816 KB	Output is correct
27	Correct	40 ms	78644 KB	Output is correct
28	Correct	41 ms	78556 KB	Output is correct
29	Correct	40 ms	78524 KB	Output is correct
30	Correct	41 ms	78480 KB	Output is correct
31	Correct	40 ms	78528 KB	Output is correct
32	Correct	43 ms	78476 KB	Output is correct
33	Correct	41 ms	78504 KB	Output is correct
34	Correct	44 ms	78532 KB	Output is correct
35	Correct	41 ms	78584 KB	Output is correct
36	Correct	80 ms	79284 KB	Output is correct
37	Correct	108 ms	80096 KB	Output is correct
38	Correct	125 ms	80652 KB	Output is correct
39	Correct	127 ms	80940 KB	Output is correct
40	Correct	111 ms	80384 KB	Output is correct
41	Correct	84 ms	79760 KB	Output is correct
42	Correct	83 ms	79716 KB	Output is correct
43	Correct	118 ms	80136 KB	Output is correct
44	Correct	41 ms	78480 KB	Output is correct
45	Correct	40 ms	78496 KB	Output is correct
46	Correct	43 ms	78532 KB	Output is correct
47	Correct	41 ms	78500 KB	Output is correct
48	Correct	39 ms	78484 KB	Output is correct
49	Correct	43 ms	78532 KB	Output is correct
50	Correct	42 ms	78532 KB	Output is correct
51	Correct	43 ms	78692 KB	Output is correct
52	Correct	46 ms	78632 KB	Output is correct
53	Correct	83 ms	79324 KB	Output is correct
54	Correct	128 ms	80756 KB	Output is correct
55	Correct	137 ms	80984 KB	Output is correct
56	Correct	119 ms	80580 KB	Output is correct
57	Correct	163 ms	81888 KB	Output is correct
58	Correct	92 ms	79492 KB	Output is correct
59	Correct	129 ms	80356 KB	Output is correct

답안 #468935

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 10.0 / 10.0

Subtask #3 8.0 / 8.0

Subtask #4 31.0 / 31.0

Subtask #5 44.0 / 44.0

Subtask #1
7.0 / 7.0

Subtask #2
10.0 / 10.0

Subtask #3
8.0 / 8.0

Subtask #4
31.0 / 31.0

Subtask #5
44.0 / 44.0