oj.uz

Submission #896716

# Submission time Handle Problem Language Result Execution time Memory
896716 2024-01-02T01:05:13 Z Isam Autobus (COCI22_autobus) C++17
30 / 70
 1000 ms 3092 KB 
#include<bits/stdc++.h>
using namespace std;
constexpr int sz = 1e5 + 53243;
constexpr int inf = 1e9 + 7;

int n, m, K, Q;

int dp[100][100][100];

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(register int i = 1; i <= 71; ++i){
		for(register int j = i; j <= 71; ++j){
			for(register int l = 0; l < 75; ++l) dp[i][j][l] = dp[j][i][l] = inf;
		}
	}
	for(register int i = 1; i <= n; ++i) dp[i][i][0] = 0;
	for(register int i = 1, a, b, t; i <= m; ++i){
		cin >> a >> b >> t;
		dp[a][b][1] = min(dp[a][b][1], t);
	}
	cin >> K >> Q;
	for(register int k = 0; k < min(K+1, n+1); ++k){
		for(register int i = 1; i <= n; ++i){
			for(register int j = 1; j <= n; ++j){
				for(register int l = 1; l <= n; ++l){
					for(register int r = 0; r <= k / 2; ++r){
						
						if(dp[i][l][r] != inf && dp[l][j][k - r] != inf) dp[i][j][k] = min(dp[i][j][k], dp[i][l][r] + dp[l][j][k - r]);
						
					}
				}
			}
		}
		
	}
	int u, v;
	while(Q--){
		cin >> u >> v;
		int ans = inf;
		for(register int i = 0; i < min(K + 1, n+1); ++i){
			ans = min(ans, dp[u][v][i]);
		}
		cout << (ans == inf ? -1 : ans) << '\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:13:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   13 |  for(register int i = 1; i <= 71; ++i){
      |                   ^
Main.cpp:14:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   14 |   for(register int j = i; j <= 71; ++j){
      |                    ^
Main.cpp:15:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   15 |    for(register int l = 0; l < 75; ++l) dp[i][j][l] = dp[j][i][l] = inf;
      |                     ^
Main.cpp:18:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   18 |  for(register int i = 1; i <= n; ++i) dp[i][i][0] = 0;
      |                   ^
Main.cpp:19:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   19 |  for(register int i = 1, a, b, t; i <= m; ++i){
      |                   ^
Main.cpp:19:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   19 |  for(register int i = 1, a, b, t; i <= m; ++i){
      |                          ^
Main.cpp:19:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   19 |  for(register int i = 1, a, b, t; i <= m; ++i){
      |                             ^
Main.cpp:19:32: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   19 |  for(register int i = 1, a, b, t; i <= m; ++i){
      |                                ^
Main.cpp:24:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   24 |  for(register int k = 0; k < min(K+1, n+1); ++k){
      |                   ^
Main.cpp:25:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 |   for(register int i = 1; i <= n; ++i){
      |                    ^
Main.cpp:26:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   26 |    for(register int j = 1; j <= n; ++j){
      |                     ^
Main.cpp:27:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   27 |     for(register int l = 1; l <= n; ++l){
      |                      ^
Main.cpp:28:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   28 |      for(register int r = 0; r <= k / 2; ++r){
      |                       ^
Main.cpp:42:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   42 |   for(register int i = 0; i < min(K + 1, n+1); ++i){
      |                    ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 4 ms 2908 KB Output is correct
4 Correct 4 ms 2908 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 5 ms 2904 KB Output is correct
7 Correct 7 ms 2904 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 91 ms 3092 KB Output is correct
8 Execution timed out 1022 ms 2904 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 4 ms 2908 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 4 ms 2908 KB Output is correct
12 Correct 5 ms 2904 KB Output is correct
13 Correct 7 ms 2904 KB Output is correct
14 Correct 91 ms 3092 KB Output is correct
15 Execution timed out 1022 ms 2904 KB Time limit exceeded
16 Halted 0 ms 0 KB -