Submission #421057

#	Time	Username	Problem	Language	Result	Execution time	Memory
421057		Alex_tz307	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	827 ms	59940 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;
using int64 = long long;

const int MAXN = 1e5;
const int64 INF = 1e18L;
bitset<MAXN> is_exit, viz;
vector<pair<int,int>> G[MAXN];
int64 d1[MAXN], d2[MAXN];

int Dijkstra(int n) {
  priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> pq;
  for (int u = 0; u < n; ++u)
    if (is_exit[u])
      pq.emplace(0, u);
    else d1[u] = d2[u] = INF;
  while (!pq.empty()) {
    int64 d;
    int u;
    tie(d, u) = pq.top();
    pq.pop();
    if (viz[u])
      continue;
    viz[u] = true;
    for (auto it : G[u]) {
      int v, w;
      tie(v, w) = it;
      if (viz[v])
        continue;
      int64 cost = d + w;
      if (d1[v] >= cost) {
        d2[v] = d1[v];
        d1[v] = cost;
      } else if (d2[v] > cost)
          d2[v] = cost;
      pq.emplace(d2[v], v);
    }
  }
  return d2[0];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  for (int i = 0; i < M; ++i) {
    int u = R[i][0], v = R[i][1], w = L[i];
    G[u].emplace_back(v, w);
    G[v].emplace_back(u, w);
  }
  for (int i = 0; i < K; ++i)
    is_exit[P[i]] = true;
  return Dijkstra(N);
}

/* int n, m, R[MAXN][2], L[MAXN], k, P[MAXN], sol;

void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}

int main() {
  fastIO();
  cin >> n >> m >> k;
  for (int i = 0; i < m; ++i)
    cin >> R[i][0] >> R[i][1] >> L[i];
  for (int i = 0; i < k; ++i)
    cin >> P[i];
  cin >> sol;
  int ans = travel_plan(n, m, R, L, k, P);
  if (ans == sol)
    cout << "OK\n";
  else {
    cout << "WA\n";
    cout << "USER OUTPUT: " << ans << '\n';
    cout << "EXPECTED ANSWER: " << sol << '\n';
  }
  return 0;
} */

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