Submission #1249673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249673		thewizardman	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	427 ms	84708 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
const static inline ll inf = 0x3f3f3f3f3f3f3f3f;

static priority_queue<pli, vector<pli>, greater<pli>> pq;
static vector<pil> adj[100000];
static ll dist[100000];
static __int8_t flag[100000];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
  memset(dist, 0x3f, sizeof dist);
  for (int i = 0; i < m; i++) adj[r[i][0]].emplace_back(r[i][1], l[i]), adj[r[i][1]].emplace_back(r[i][0], l[i]);
  for (int i = 0; i < k; i++) flag[p[i]] = 1, pq.emplace(dist[p[i]] = 0, p[i]);
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (flag[u] == 0) { flag[u] = 1; continue; }
    if (flag[u] == 2) continue;
    flag[u] = 2; dist[u] = d;
    for (auto& [v, w]: adj[u]) if (flag[v] != 2) pq.emplace(dist[u] + w, v);
  }
  // for (int i = 0; i < n; i++) cerr << (int) flag[i] << ' ' << dist[i] << '\n';
  return dist[0];
}

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