oj.uz

Submission #244708

# Submission time Handle Problem Language Result Execution time Memory
244708 2020-07-04T16:21:31 Z santaclaus03 Toll (BOI17_toll) C++14
46 / 100
 3000 ms 5556 KB 
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vvii = vector<vector<ii>>;

#define INF 1000000000

int main()
{
    int K, n, m, o;
    cin >> K >> n >> m >> o;
    vvii rev(n);
    for (int i = 0; i < m; ++i)
    {
        int a, b, t;
        cin >> a >> b >> t;
        rev[b].emplace_back(t, a);
    }
    for (int i = 0; i < o; ++i)
    {
        int a, b;
        cin >> a >> b;
        vi dist(n, INF);
        dist[a] = 0;
        for (int u = a + 1; u < n; ++u)
        {
            for (ii e : rev[u])
            {
                dist[u] = min(dist[u], dist[e.second] + e.first);
            }
        }
        int ans = dist[b];
        cout << (ans == INF ? -1 : ans) << endl;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1759 ms 3528 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 13 ms 384 KB Output is correct
6 Correct 11 ms 384 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 1746 ms 3700 KB Output is correct
9 Correct 1650 ms 3504 KB Output is correct
10 Correct 506 ms 1856 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 10 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 86 ms 3576 KB Output is correct
11 Correct 165 ms 3636 KB Output is correct
12 Correct 212 ms 4472 KB Output is correct
13 Correct 223 ms 4600 KB Output is correct
14 Correct 180 ms 4020 KB Output is correct
15 Correct 133 ms 2680 KB Output is correct
16 Correct 119 ms 2812 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 10 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 86 ms 3576 KB Output is correct
11 Correct 165 ms 3636 KB Output is correct
12 Correct 212 ms 4472 KB Output is correct
13 Correct 223 ms 4600 KB Output is correct
14 Correct 180 ms 4020 KB Output is correct
15 Correct 133 ms 2680 KB Output is correct
16 Correct 119 ms 2812 KB Output is correct
17 Correct 824 ms 3912 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Correct 4 ms 256 KB Output is correct
21 Correct 5 ms 256 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 23 ms 384 KB Output is correct
24 Correct 25 ms 384 KB Output is correct
25 Correct 37 ms 512 KB Output is correct
26 Correct 32 ms 512 KB Output is correct
27 Correct 575 ms 3892 KB Output is correct
28 Correct 1258 ms 4788 KB Output is correct
29 Correct 1204 ms 5556 KB Output is correct
30 Correct 1184 ms 4912 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1759 ms 3528 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 13 ms 384 KB Output is correct
6 Correct 11 ms 384 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 1746 ms 3700 KB Output is correct
9 Correct 1650 ms 3504 KB Output is correct
10 Correct 506 ms 1856 KB Output is correct
11 Execution timed out 3073 ms 3636 KB Time limit exceeded
12 Halted 0 ms 0 KB -