Submission #297783

#	Time	Username	Problem	Language	Result	Execution time	Memory
297783		Haunted_Cpp	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	2 ms	2688 KiB

crocodile

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

typedef long long i64;
const int MAX_N = 1e5 + 5;

vector<vector<pair<int, int>>> g(MAX_N);
bitset<MAX_N> is_exit;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  for (int i = 0; i < M; i++) {
    g[R[i][0]].emplace_back(R[i][1], L[i]);
    g[R[i][1]].emplace_back(R[i][0], L[i]);
  }
  for (int i = 0; i < K; i++) {
    is_exit[P[i]] = 1;
  }
  auto Dijkstra = [&](int is_blocked) {
    vector<i64> dist(N, 1e18);
    priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
    dist[0] = 0;
    pq.emplace(dist[0], 0);
    while(!pq.empty()) {
      auto [w, node] = pq.top();
      pq.pop();
      if (w != dist[node]) {
        continue;
      }
      for (auto [to, cost] : g[node]) {
        if (to == is_blocked) {
          continue;
        }
        if (dist[to] > dist[node] + cost) {
          dist[to] = dist[node] + cost;
          pq.emplace(dist[to], to);
        }
      }
    }
    i64 mn = 1e18;
    for (int i = 0; i < N; i++) {
      if (is_exit[i] && is_blocked != i) {
        mn = min(mn, dist[i]);
      }
    }
    return mn;
  };
  
  i64 best_way = 0;
  for (int i = 0; i < K; i++) {
    best_way = max(best_way, Dijkstra(P[i]));
  }
  return best_way;
}

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