Submission #1138600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138600		kitkat12	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	286 ms	72984 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
//using u64 = uint64_t;
//using u128 = __uint128_t;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    const ll inf = 1e18;
    vector<pair<int,ll>> adj[n];
    li(i,0,m){
        adj[r[i][0]].pb({r[i][1],l[i]});
        adj[r[i][1]].pb({r[i][0],l[i]});
    }
    vector<pair<ll,ll>> d(n, {inf,inf}); //best,second best
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    li(i,0,k){
        pq.push({0,p[i]});
        d[p[i]] = {0,0};
    }
    while(!pq.empty()){
        auto [d_v, v] = pq.top();
        pq.pop();
        if(d_v>d[v].S)continue;
        for(const auto [to,len] : adj[v]){
            if(d_v+len < d[to].F){
                if(d[to].F<d[to].S)pq.push({d[to].F,to});
                d[to].S = d[to].F;
                d[to].F = d_v+len;
            }
            else if(d_v+len < d[to].S){
                d[to].S = d_v+len;
                pq.push({d[to].S,to});
            }
        }
    }
    return d[0].S;
}

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