oj.uz

Submission #896713

# Submission time Handle Problem Language Result Execution time Memory
896713 2024-01-02T00:55:27 Z Isam Autobus (COCI22_autobus) C++17
15 / 70
 1000 ms 12808 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[200][200][200];

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 < 100; ++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 < 100; ++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; ++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, 100); ++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 < 100; ++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:25:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 |  for(register int k = 0; k < 100; ++k){
      |                   ^
Main.cpp:26:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   26 |   for(register int i = 1; i <= n; ++i){
      |                    ^
Main.cpp:27:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   27 |    for(register int j = 1; j <= n; ++j){
      |                     ^
Main.cpp:28:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   28 |     for(register int l = 1; l <= n; ++l){
      |                      ^
Main.cpp:29:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   29 |      for(register int r = 0; r <= k; ++r){
      |                       ^
Main.cpp:43:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   43 |   for(register int i = 0; i < min(K + 1, 100); ++i){
      |                    ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 4 ms 12808 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 12636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 4 ms 12808 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct
7 Execution timed out 1058 ms 12636 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 4 ms 12808 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct
7 Execution timed out 1052 ms 12636 KB Time limit exceeded
8 Halted 0 ms 0 KB -