oj.uz

Submission #291024

# Submission time Handle Problem Language Result Execution time Memory
291024 2020-09-04T15:40:11 Z Kastanda Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 769 ms 52332 KB 
// M
#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, k, M[N];
ll D[N][2];
vector < pair < int , int > > Adj[N];

int travel_plan(int _n, int _m, int R[][2], int L[], int _k, int P[])
{
        n = _n; m = _m; k = _k;
        for (int i = 0; i < m; i ++)
        {
                Adj[R[i][0]].push_back({R[i][1], L[i]});
                Adj[R[i][1]].push_back({R[i][0], L[i]});
        }

        memset(D, 63, sizeof(D));
        priority_queue < pair < ll , int > > Pq;
        for (int i = 0; i < k; i ++)
                D[P[i]][0] = D[P[i]][1] = 0, Pq.push({0, P[i]});
        while (Pq.size())
        {
                int v = Pq.top().second;
                Pq.pop();
                if (M[v])
                        continue;
                M[v] = 1;
                for (auto e : Adj[v])
                {
                        int u = e.first;
                        int w = e.second;
                        if (D[u][0] > D[v][1] + w)
                        {
                                D[u][1] = D[u][0];
                                D[u][0] = D[v][1] + w;
                                Pq.push({-D[u][1], u});
                        }
                        else if (D[u][1] > D[v][1] + w)
                        {
                                D[u][1] = D[v][1] + w;
                                Pq.push({-D[u][1], u});
                        }
                }
        }
        return D[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 4 ms 4384 KB Output is correct
6 Correct 4 ms 4352 KB Output is correct
7 Correct 4 ms 4352 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 5 ms 4480 KB Output is correct
10 Correct 3 ms 4224 KB Output is correct
11 Correct 4 ms 4352 KB Output is correct
12 Correct 7 ms 4608 KB Output is correct
13 Correct 7 ms 4736 KB Output is correct
14 Correct 3 ms 4224 KB Output is correct
15 Correct 4 ms 4352 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 4 ms 4384 KB Output is correct
6 Correct 4 ms 4352 KB Output is correct
7 Correct 4 ms 4352 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 5 ms 4480 KB Output is correct
10 Correct 3 ms 4224 KB Output is correct
11 Correct 4 ms 4352 KB Output is correct
12 Correct 7 ms 4608 KB Output is correct
13 Correct 7 ms 4736 KB Output is correct
14 Correct 3 ms 4224 KB Output is correct
15 Correct 4 ms 4352 KB Output is correct
16 Correct 585 ms 45668 KB Output is correct
17 Correct 117 ms 13808 KB Output is correct
18 Correct 145 ms 15216 KB Output is correct
19 Correct 769 ms 52332 KB Output is correct
20 Correct 353 ms 38308 KB Output is correct
21 Correct 53 ms 8312 KB Output is correct
22 Correct 390 ms 33980 KB Output is correct