oj.uz

Submission #764160

# Submission time Handle Problem Language Result Execution time Memory
764160 2023-06-23T08:01:57 Z boris_mihov Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 857 ms 62928 KB 
#include "crocodile.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 2e9;

struct Node
{
    int min;
    int min2;
    int node;

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

int n, m;
int min[MAXN];
int min2[MAXN];
int dist[MAXN];
bool vis[MAXN];
std::set <Node> s;
std::vector <std::pair <int,int>> g[MAXN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N; m = M;
    for (int i = 0 ; i < m ; ++i)
    {
        g[R[i][0] + 1].push_back({R[i][1] + 1, L[i]});
        g[R[i][1] + 1].push_back({R[i][0] + 1, L[i]});
    }

    std::fill(min + 1, min + 1 + n, INF);
    std::fill(min2 + 1, min2 + 1 + n, INF);

    for (int i = 0 ; i < K ; ++i)
    {
        min[P[i] + 1] = min2[P[i] + 1] = 0;
    }

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

    while (!s.empty())
    {
        auto [currMIN, currDist, node] = (*s.begin());
        s.erase(s.begin());

        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, dist] : g[node])
        {
            if (vis[u])
            {
                continue;
            }

            s.erase(s.find({min[u], min2[u], u}));
            if (min[u] > currDist + dist)
            {
                min2[u] = min[u];
                min[u] = currDist + dist;
            } else if (min2[u] > currDist + dist)
            {
                min2[u] = currDist + dist;
            }

            s.insert({min[u], min2[u], u});
        }
    }

    return min2[1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 3 ms 2812 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 2 ms 2716 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 6 ms 3088 KB Output is correct
13 Correct 7 ms 3188 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 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 3 ms 2812 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 2 ms 2716 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 6 ms 3088 KB Output is correct
13 Correct 7 ms 3188 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 712 ms 56156 KB Output is correct
17 Correct 97 ms 20076 KB Output is correct
18 Correct 142 ms 21568 KB Output is correct
19 Correct 857 ms 62928 KB Output is correct
20 Correct 321 ms 49484 KB Output is correct
21 Correct 47 ms 9596 KB Output is correct
22 Correct 374 ms 47832 KB Output is correct