oj.uz

Submission #534827

# Submission time Handle Problem Language Result Execution time Memory
534827 2022-03-09T03:17:58 Z phathnv Autobus (COCI22_autobus) C++11
30 / 70
 1000 ms 1880 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 75;

int n, m, dp[N][N][N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int u = 1; u <= n; ++u) {
            for (int v = 1; v <= n; ++v) {
                dp[i][u][v] = (u != v? 1e9 : 0);
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        dp[1][u][v] = min(dp[1][u][v], c);
    }
    for (int i = 2; i <= n; ++i) {
        for (int u = 1; u <= n; ++u) {
            for (int v = 1; v <= n; ++v) {
                dp[i][u][v] = dp[i - 1][u][v];
            }
        }
        for (int j = 1; j < i; ++j) {
            for (int u = 1; u <= n; ++u) {
                for (int v = 1; v <= n; ++v) {
                    for (int k = 1; k <= n; ++k) {
                        dp[i][u][v] = min(dp[i][u][v], dp[j][u][k] + dp[i - j][k][v]);
                    }
                }
            }
        }
    }
    int k, q;
    cin >> k >> q;
    k = min(k, n);
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        cout << (dp[k][u][v] == 1e9? -1 : dp[k][u][v]) << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 1860 KB Output is correct
2 Correct 886 ms 1840 KB Output is correct
3 Correct 916 ms 1868 KB Output is correct
4 Correct 916 ms 1848 KB Output is correct
5 Correct 902 ms 1868 KB Output is correct
6 Correct 886 ms 1868 KB Output is correct
7 Correct 915 ms 1872 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 889 ms 1868 KB Output is correct
8 Correct 927 ms 1868 KB Output is correct
9 Correct 968 ms 1848 KB Output is correct
10 Correct 931 ms 1864 KB Output is correct
11 Execution timed out 1004 ms 1880 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 907 ms 1860 KB Output is correct
8 Correct 886 ms 1840 KB Output is correct
9 Correct 916 ms 1868 KB Output is correct
10 Correct 916 ms 1848 KB Output is correct
11 Correct 902 ms 1868 KB Output is correct
12 Correct 886 ms 1868 KB Output is correct
13 Correct 915 ms 1872 KB Output is correct
14 Correct 889 ms 1868 KB Output is correct
15 Correct 927 ms 1868 KB Output is correct
16 Correct 968 ms 1848 KB Output is correct
17 Correct 931 ms 1864 KB Output is correct
18 Execution timed out 1004 ms 1880 KB Time limit exceeded
19 Halted 0 ms 0 KB -