Submission #1213110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213110		kunzaZa183	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	1656 ms	109124 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  vector<vector<pair<int, int>>> adj(N);
  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]);
  }

  ll bign = 1e18;
  vector<pair<ll, ll>> stat(N, {bign, bign});

  // value, curin
  priority_queue<pair<ll, int>> pqai3;
  for (int i = 0; i < K; i++) {
    stat[P[i]] = {0, 0};
    for (auto a : adj[P[i]]) {
      pqai3.emplace(-a.second, a.first);
    }
  }

  while (!pqai3.empty()) {
    pair<ll, int> pii = pqai3.top();
    pqai3.pop();

    if (-pii.first >= stat[pii.second].second) continue;

    if (-pii.first >= stat[pii.second].first)
      stat[pii.second].second = -pii.first;
    else {
      stat[pii.second].second = stat[pii.second].first;
      stat[pii.second].first = -pii.first;
    }

    for (auto a : adj[pii.second])
      pqai3.emplace(-(stat[pii.second].second + a.second), a.first);
  }

  // for (int i = 0; i < N; i++) {
  //   cout << stat[i].first << " " << stat[i].second << "\n";
  // }

  return stat[0].second;
}

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