Submission #1218983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218983		niwrad	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	1821 ms	327680 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  int n = M;
  vector<vector<pair<int, long long>>> graph(N);
  vector<int> vis(n);
  vector<multiset<long long>> dis(n);
  for (int i = 0; i < M; i++) {
    graph[R[i][0]].push_back({R[i][1], L[i]});
    graph[R[i][1]].push_back({R[i][0], L[i]});
  }
  priority_queue<pair<long long, int>> pq;
  for (int i = 0; i < K; i++) {
    vis[P[i]] = 1;
    for (auto adj : graph[P[i]]) {
      if (!vis[adj.first]) {
        dis[adj.first].insert(adj.second);
        if (dis[adj.first].size() > 1) {
          auto it = dis[adj.first].begin();
          it++;
          pq.push({-*it, adj.first});
        }
      }
    }
  }
  while (pq.size() > 0) {
    auto t = pq.top();
    pq.pop();
    if (vis[t.second]) {
      continue;
    }
    long long d = -t.first;
    for (auto adj : graph[t.second]) {
      if (!vis[adj.first]) {
        dis[adj.first].insert(d + adj.second);
        if (dis[adj.first].size() > 1) {
          auto it = dis[adj.first].begin();
          it++;
          pq.push({-*it, adj.first});
        }
      }
    }
  }
  auto it = dis[0].begin();
  it++;
  return *it;
}

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