oj.uz

Submission #124039

# Submission time Handle Problem Language Result Execution time Memory
124039 2019-07-02T12:01:21 Z johutha Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 923 ms 67048 KB 
#include "crocodile.h"
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

vector<int> vals;

vector<vector<pair<int,int>>> adjlist;

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
	vals.resize(n, -1);
	adjlist.resize(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<int,int>> pq;
	for (int i = 0; i < k; i++)
	{
        vals[P[i]] = -2;
        pq.push({0, P[i]});
	}
    while (!pq.empty())
    {
        int curr = pq.top().second;
        int val = -pq.top().first;
        pq.pop();
        if (vals[curr] == -1)
        {
            vals[curr] = -2;
            continue;
        }
        if (vals[curr] > -1) continue;
        vals[curr] = val;
        for (auto p : adjlist[curr])
        {
            if (vals[p.first] > -1) continue;
            pq.push({-vals[curr] - p.second, p.first});
        }
    }
    return vals[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 7 ms 1016 KB Output is correct
13 Correct 7 ms 1016 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 7 ms 1016 KB Output is correct
13 Correct 7 ms 1016 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 834 ms 62792 KB Output is correct
17 Correct 101 ms 13304 KB Output is correct
18 Correct 126 ms 14840 KB Output is correct
19 Correct 923 ms 67048 KB Output is correct
20 Correct 534 ms 55780 KB Output is correct
21 Correct 51 ms 5880 KB Output is correct
22 Correct 510 ms 44596 KB Output is correct