oj.uz

Submission #372850

# Submission time Handle Problem Language Result Execution time Memory
372850 2021-03-02T02:24:36 Z ntabc05101 Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 7 ms 492 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int64_t inf = 1e17;
const int max_n = 100000;
const int max_m = 100000;

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][0], l[i]});
                adjList[r[i][1]].push_back({r[i][1], 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 (auto& to: adjList[cvertex]) {
                                pq.push({-(cdist+to.s), to.f});
                        }
                }
        }
        
        return distList[0][1];
}

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

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

        cout << travel_paln(n, m, r, l, k, p);

        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
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -