oj.uz

Submission #764656

# Submission time Handle Problem Language Result Execution time Memory
764656 2023-06-23T18:09:10 Z borisAngelov Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 855 ms 62848 KB 
#include "crocodile.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int maxn = 100005;
const int inf = 1e9 + 5;

int n, m, k;

vector<pair<int, int>> g[maxn];

struct vertex
{
    int min1;
    int min2;
    int node;

    friend bool operator < (const vertex& a, const vertex& b)
    {
        return a.min2 < b.min2 || (a.min2 == b.min2 && a.node < b.node);
    }
};

set<vertex> s;

bool visited[maxn];

int dist[maxn];
int dist2[maxn];

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)
    {
        int x = R[i][0];
        int y = R[i][1];
        int w = L[i];

        ++x;
        ++y;

        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
        dist2[i] = inf;
    }

    for (int i = 0; i < k; ++i)
    {
        dist[P[i] + 1] = 0;
        dist2[P[i] + 1] = 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        s.insert({dist[i], dist2[i], i});
    }

    while (!s.empty())
    {
        auto [best, second_best, node] = (*s.begin());

        s.erase(s.begin());

        if (visited[node] == true)
        {
            continue;
        }

        visited[node] = true;

        for (auto [next_node, w] : g[node])
        {
            if (visited[next_node] == false)
            {
                s.erase({dist[next_node], dist2[next_node], next_node});

                int new_dist = second_best + w;

                if (dist[next_node] > new_dist)
                {
                    dist2[next_node] = dist[next_node];
                    dist[next_node] = new_dist;
                }
                else if (dist2[next_node] > new_dist)
                {
                    dist2[next_node] = new_dist;
                }

                s.insert({dist[next_node], dist2[next_node], next_node});
            }
        }
    }

    return dist2[1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2676 KB Output is correct
12 Correct 5 ms 3056 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2676 KB Output is correct
12 Correct 5 ms 3056 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 715 ms 56148 KB Output is correct
17 Correct 97 ms 20104 KB Output is correct
18 Correct 141 ms 21568 KB Output is correct
19 Correct 855 ms 62848 KB Output is correct
20 Correct 344 ms 49608 KB Output is correct
21 Correct 47 ms 9512 KB Output is correct
22 Correct 374 ms 47808 KB Output is correct