Submission #1302119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302119		proplayer	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	259 ms	50664 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int maxN = 1e6 + 5;
int n, m, k, p[maxN];
struct Tedge
{
    int u, v;
    ll w;
}
e[maxN];
vector<int> adj[maxN];
ll d1[maxN], d2[maxN];
struct Titem
{
    int v;
    ll dlab;
    bool operator < (const Titem& other) const
    {
        return dlab > other.dlab;
    }
    bool valid()
    {
        return dlab == d2[v];
    }
};
priority_queue<Titem> pq;
void Dijkstra()
{
    fill(d1 + 1, d1 + n + 1, 1e18);
    fill(d2 + 1, d2 + n + 1, 1e18);
    for (int i = 1; i <= k; ++i)
    {
        d1[p[i]] = d2[p[i]] = 0;
        pq.push({p[i], d1[p[i]]});
    }
    while (!pq.empty())
    {
        Titem tmp = pq.top(); pq.pop();
        if (!tmp.valid()) continue;
        int u = tmp.v;
        //cerr << u << " " << d2[u] << "\n";
        if (u == 1) return;
        for (int i : adj[u])
        {
            int v = e[i].u ^ e[i].v ^ u;
            if (d1[v] > d2[u] + e[i].w)
            {
                if (d1[v] < d2[v])
                {
                    d2[v] = d1[v];
                    pq.push({v, d2[v]});
                }
                d1[v] = d2[u] + e[i].w;
            }
            else if (d2[v] > d2[u] + e[i].w)
            {
                d2[v] = d2[u] + e[i].w;
                pq.push({v, d2[v]});
            }
        }
    }
}
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 = 1; i <= m; ++i)
    {
        e[i].u = R[i - 1][0] + 1;
        e[i].v = R[i - 1][1] + 1;
        e[i].w = L[i - 1];
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
    for (int i = 1; i <= k; ++i)
    {
        p[i] = P[i - 1] + 1;
    }
    Dijkstra();
    return d2[1];
}

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