oj.uz

Submission #372853

# Submission time Handle Problem Language Result Execution time Memory
372853 2021-03-02T02:41:13 Z ntabc05101 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1447 ms 93800 KB 
#include<bits/stdc++.h>
using namespace std;

int64_t travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {        
        vector< pair<int, int> > adjList[n];
        for (int i = 0; i < m; i++) {
                adjList[r[i][0]].push_back({r[i][1], l[i]});
                adjList[r[i][1]].push_back({r[i][0], l[i]});
        }

        priority_queue< pair<int64_t, int> > pq;
        vector<int64_t> distList[n];
        for (int i=0; i<k; ++i) {
                distList[p[i]].push_back(0);
                pq.push({-0, p[i]});
        }

        while (!pq.empty()) {
                int64_t cdist = -pq.top().first;
                int cvertex = pq.top().second;

                //cout << cdist << " " << cvertex << "\n";
                pq.pop();

                if (distList[cvertex].size() > 1) continue;
                distList[cvertex].push_back(cdist);
                if (distList[cvertex].size() == 2) {
                        for (pair<int, int>& to: adjList[cvertex]) {
                                pq.push({-(cdist+to.second), to.first});
                        }
                }
        }

        return distList[0][1];
}

/*int main() {
        ios_base::sync_with_stdio(0); cin.tie(0);

        int n, m, k; cin >> n >> m >> k;
        int r[m][2], l[m];
        for (int i = 0; i < m; i++) {
                cin >> r[i][0] >> r[i][1] >> l[i];
        }
        int p[k];
        for (int i = 0; i < k; i++) {
                cin >> p[i];
        }

        cout << travel_plan(n, m, r, l, k, p) << "\n";

        return 0;
}*/

/*
5 4 3
0 1
0 2
3 2
2 4
2 3 1 4
1 3 4
*/

/*
5 7 2
0 2
0 3
3 2
2 1
0 1
0 4
3 4
4 3 2 10 100 7 9
1 3
*/

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 8 ms 1516 KB Output is correct
13 Correct 7 ms 1512 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 8 ms 1516 KB Output is correct
13 Correct 7 ms 1512 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 1292 ms 88312 KB Output is correct
17 Correct 112 ms 18432 KB Output is correct
18 Correct 176 ms 19692 KB Output is correct
19 Correct 1447 ms 93800 KB Output is correct
20 Correct 780 ms 80256 KB Output is correct
21 Correct 57 ms 7660 KB Output is correct
22 Correct 641 ms 46692 KB Output is correct