Submission #221446

#	Time	Username	Problem	Language	Result	Execution time	Memory
221446		emil_physmath	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	2081 ms	175112 KiB

crocodile

#include "crocodile.h"
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long llong;
const llong inf = 1000000000000000LL;
struct Jump
{
    operator int&()
    {
        return to;
    }

    int to;
    llong len;
};

vector<Jump> jumps[100000];
multiset<llong> s[100000];

inline llong D(const multiset<llong>& s)
{
    if (s.empty()) return inf;
    if (s.size() >= 2) return *next(s.begin());
    if (*s.begin()) return inf;
    return 0;
}
int travel_plan(int n, int m, int edges[][2], int l[], int k, int p[])
{
    for (int i = 0; i < m; ++i)
    {
        int u = edges[i][0], v = edges[i][1], w = l[i];
        jumps[u].push_back({v, w});
        jumps[v].push_back({u, w});
    }
    vector<llong> d(n, inf), prevd(n, inf);
    priority_queue<pair<int, int> > q;
    for (int i = 0; i < k; ++i)
    {
        prevd[p[i]] = d[p[i]] = 0;
        q.push({0, p[i]});
    }
    for (int v = 0; v < n; ++v)
        for (Jump to: jumps[v])
            s[v].insert(d[to] + to.len);
    while (!q.empty())
    {
        int v = q.top().second;
        if (d[v] != -q.top().first)
        {
            q.pop();
            continue;
        }
        q.pop();
        // cerr << v << ": " << d[v] << '\n';
        for (Jump to: jumps[v])
        {
            s[to].erase(s[to].find(prevd[v] + to.len));
            s[to].insert(d[v] + to.len);
            if (D(s[to]) < d[to])
            {
                // swap(d[to], prevd[to]);
                d[to] = D(s[to]);
                q.push({-d[to], to});
            }
        }
    }
    return d[0];
}

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