Submission #654982

#	Time	Username	Problem	Language	Result	Execution time	Memory
654982		noedit	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	2 ms	2644 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;

const int MAXN = 1e5;

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

vector<int> mark;
vector<long long> 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<pair<long long, int> > st;
    for (int i = 0; i < k; i++)
    {
        d1[mark[i]] = 0;
        d2[mark[i]] = 0;
        st.insert({0, mark[i]});
    }
    while (!st.empty())
    {
        auto[mn2, v] = *st.begin();
        st.erase(st.begin());
        for (auto&[u, w] : g[v])
        {
            if (d1[u] > mn2 + w)
            {
                d2[u] = d1[u];
                st.insert({d2[u], u});
                d1[u] = mn2 + w;
            }
            else
            {
                if (d2[u] > mn2 + w)
                {
                    //st.erase({d2[u], u});
                    d2[u] = mn2 + w;
                    st.insert({d2[u], u});
                }
            }
        }
    }
    return d2[0];
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11