Submission #1154402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154402		hiderr	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	939 ms	75992 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back

using ll = long long;
vector<vector<pair<int, int>>> graph;

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
  graph.resize(n);

  loop(i, 0, m-1) {
    graph[R[i][0]].pb({ R[i][1], L[i] });
    graph[R[i][1]].pb({ R[i][0], L[i] });
  }

  using pq_t = pair<ll, int>;
  priority_queue<pq_t, vector<pq_t>, greater<pq_t>> pq;

  vector<int> vis(n + 1);
  vector<ll> dist(n + 1);

  loop(i, 0, k-1) {
    pq.push({ 0, P[i] });
    vis[P[i]] = 1;
  }

  while(!pq.empty()) {
    auto [ d, v ] = pq.top(); pq.pop();
    ++vis[v];
    if(vis[v] != 2) {
      continue;
    }
    dist[v] = d;
    for(auto [ s, w ] : graph[v]) {
      pq.push({ d + w, s });
    }
  }

  return dist[0];

}

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