oj.uz

Submission #1096650

# Submission time Handle Problem Language Result Execution time Memory
1096650 2024-10-04T23:36:00 Z raphaelp Treasure Hunt (CCO24_day1problem1) C++14
25 / 25
 2124 ms 122424 KB 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> Tab(N);
    for (int i = 0; i < N; i++)
        cin >> Tab[i];
    vector<vector<pair<int, int>>> AR(N);
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        AR[a].push_back({b, c});
        AR[b].push_back({a, c});
    }
    priority_queue<pair<int, int>> PQ;
    for (int i = 0; i < N; i++)
        PQ.push({Tab[i], i});
    vector<int> best(N, -1);
    while (!PQ.empty())
    {
        int x = PQ.top().second, y = PQ.top().first;
        PQ.pop();
        if (best[x] != -1)
            continue;
        best[x] = y;
        for (int i = 0; i < AR[x].size(); i++)
        {
            PQ.push({y - AR[x][i].second, AR[x][i].first});
        }
    }
    for (int i = 0; i < N; i++)
    {
        cout << best[i] << '\n';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i = 0; i < AR[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1726 ms 111220 KB Output is correct
2 Correct 1554 ms 111044 KB Output is correct
3 Correct 1693 ms 111044 KB Output is correct
4 Correct 1594 ms 111028 KB Output is correct
5 Correct 1560 ms 106528 KB Output is correct
6 Correct 1678 ms 106264 KB Output is correct
7 Correct 1489 ms 100664 KB Output is correct
8 Correct 1588 ms 100408 KB Output is correct
9 Correct 1526 ms 94052 KB Output is correct
10 Correct 1479 ms 93880 KB Output is correct
11 Correct 1353 ms 87204 KB Output is correct
12 Correct 1398 ms 87212 KB Output is correct
13 Correct 1226 ms 80544 KB Output is correct
14 Correct 1343 ms 80556 KB Output is correct
15 Correct 904 ms 53160 KB Output is correct
16 Correct 883 ms 53176 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2021 ms 122264 KB Output is correct
2 Correct 2124 ms 122268 KB Output is correct
3 Correct 1951 ms 122272 KB Output is correct
4 Correct 1940 ms 122012 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1831 ms 116408 KB Output is correct
8 Correct 1647 ms 115276 KB Output is correct
9 Correct 1492 ms 111196 KB Output is correct
10 Correct 1675 ms 112080 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1726 ms 111220 KB Output is correct
16 Correct 1554 ms 111044 KB Output is correct
17 Correct 1693 ms 111044 KB Output is correct
18 Correct 1594 ms 111028 KB Output is correct
19 Correct 1560 ms 106528 KB Output is correct
20 Correct 1678 ms 106264 KB Output is correct
21 Correct 1489 ms 100664 KB Output is correct
22 Correct 1588 ms 100408 KB Output is correct
23 Correct 1526 ms 94052 KB Output is correct
24 Correct 1479 ms 93880 KB Output is correct
25 Correct 1353 ms 87204 KB Output is correct
26 Correct 1398 ms 87212 KB Output is correct
27 Correct 1226 ms 80544 KB Output is correct
28 Correct 1343 ms 80556 KB Output is correct
29 Correct 904 ms 53160 KB Output is correct
30 Correct 883 ms 53176 KB Output is correct
31 Correct 2021 ms 122264 KB Output is correct
32 Correct 2124 ms 122268 KB Output is correct
33 Correct 1951 ms 122272 KB Output is correct
34 Correct 1940 ms 122012 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1831 ms 116408 KB Output is correct
38 Correct 1647 ms 115276 KB Output is correct
39 Correct 1492 ms 111196 KB Output is correct
40 Correct 1675 ms 112080 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 1992 ms 122424 KB Output is correct
43 Correct 1911 ms 122416 KB Output is correct
44 Correct 1582 ms 111304 KB Output is correct
45 Correct 1596 ms 111940 KB Output is correct
46 Correct 1609 ms 113076 KB Output is correct
47 Correct 1938 ms 116896 KB Output is correct
48 Correct 1694 ms 108252 KB Output is correct
49 Correct 1830 ms 111236 KB Output is correct
50 Correct 1684 ms 104612 KB Output is correct
51 Correct 961 ms 62272 KB Output is correct
52 Correct 922 ms 61548 KB Output is correct
53 Correct 863 ms 59828 KB Output is correct
54 Correct 791 ms 56284 KB Output is correct
55 Correct 1747 ms 114156 KB Output is correct
56 Correct 1611 ms 112976 KB Output is correct
57 Correct 828 ms 83116 KB Output is correct