Submission #1150711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150711		DON_F	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	1 ms	580 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define L(i, b, e) for (int i = b; i < e; ++i)
#define R(i, b, e) for (int i = b; i >= e; --i)
#define pb emplace_back
#define vi vector<int>
#define sz(x) ((int) x.size())
const int N = 1e6 + 7, Mx = 1e9 + 9;

int travel_plan(int n, int m, int e[][2], int w[], int k, int p[]){
    vector<pair<int, int>> g[n];
    L(i, 0, m){
        g[e[i][0]].pb(e[i][1], w[i]);
        g[e[i][1]].pb(e[i][0], w[i]);
    }
    vector<pair<ll, ll>> dis(n, {Mx, Mx});
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    L(i, 0, k){
        dis[p[i]].first = 0;
        pq.push({0, p[i]});
    }
    while (!pq.empty()){
        auto [d, x] = pq.top();
        pq.pop();
        if (dis[x].first != d)continue;
        for (auto &[b, t] : g[x]){
            if (d + t < dis[b].second){
                swap(dis[b].first, dis[b].second);
                dis[b].second = d + t;
                if (dis[b].first != Mx){
                    pq.push({dis[b].first, b});
                }
            }else if (d + t < dis[b].first){
                dis[b].first = d + t;
                pq.push({dis[b].first, b});
            }
        }
    }
    //assert(dis[0].first == 1LL * Mx * Mx);
    return dis[0].first;
}

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