Submission #1358459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1358459		waygonz	Crocodile's Underground City (IOI11_crocodile)	C++20	89 / 100	262 ms	77084 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>

using namespace std;

const int inf = 1e18;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<pii> adj[N];
    ll dis[2][N];
    for (int i = 0; i < N; i++) dis[0][i] = dis[1][i] = inf;
    for (int i = 0; i < M; i++) {
        int u = R[i][0], v = R[i][1];
        adj[u].emplace_back(L[i], v);
        adj[v].emplace_back(L[i], u);
    }
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for (int i = 0; i < K; i++) dis[0][P[i]] = dis[1][P[i]] = 0, q.emplace(0, P[i]);
    while (!q.empty()) {
        auto [w, u] = q.top();
        q.pop();
        if (w > dis[1][u] || w == inf) continue;
        for (auto &[ww, v] : adj[u]) {
            if (ww + w < dis[0][v]) dis[1][v] = dis[0][v], dis[0][v] = ww + w, q.emplace(dis[1][v], v);
            else if (ww + w < dis[1][v]) dis[1][v] = ww + w, q.emplace(dis[1][v], v);
        }
    }
    return (int)dis[1][0];
}

Compilation message (stderr)

crocodile.cpp:8:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | const int inf = 1e18;
      |                 ^~~~

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