oj.uz

Submission #654868

# Submission time Handle Problem Language Result Execution time Memory
654868 2022-11-01T19:49:12 Z noedit Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2 ms 2656 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

const int MAXN = 1e5;

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

vector<int> mark, d1, d2;

int n, m, k;

struct my
{
    int mn1 = INF, mn2 = INF, v = -1;
    my() {}
    my(int mn1, int mn2, int v) : mn1(mn1), mn2(mn2), v(v) {}
    bool operator<(const my& o) const
    {
        if (mn1 != o.mn1)
        {
            return mn1 < o.mn1;
        }
        if (mn2 != o.mn2)
        {
            return mn2 < o.mn2;
        }
        return v < o.v;
    }
};

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]].push_back({R[i][1], L[i]});
        g[R[i][1]].push_back({R[i][0], L[i]});
    }
    k = K;
    mark.resize(k);
    d1.resize(n, INF);
    d2.resize(n, INF);
    for (int i = 0; i < k; i++)
    {
        mark[i] = P[i];
    }
    set<my> st;
    for (int i = 0; i < k; i++)
    {
        d1[mark[i]] = 0;
        d2[mark[i]] = 0;
        st.insert({0, 0, mark[i]});
    }
    while (!st.empty())
    {
        auto[mn1, mn2, v] = *st.begin();

        st.erase(st.begin());
        if (mn2 == INF)
            continue;
        for (auto&[u, w] : g[v])
        {
            if (d1[u] > mn2 + w)
            {
                st.erase({d1[u], d2[u], u});
                d2[u] = d1[u];
                d1[u] = mn2 + w;
                st.insert({d1[u], d2[u], u});
            }
            else
            {
                if (d2[u] > mn2 + w)
                {
                    st.erase({d1[u], d2[u], u});
                    d2[u] = mn2 + w;
                    st.insert({d1[u], d2[u], u});
                }
            }
        }
    }
    return d2[0];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -