Submission #445304

#	Time	Username	Problem	Language	Result	Execution time	Memory
445304		prvocislo	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1434 ms	62640 KiB

crocodile

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

const int inf = 1e9 + 5;
int travel_plan(int n, int m, int e[][2], int l[], int k, int p[])
{
  vector<vector<pair<int, int> > > g(n);
  for (int i = 0; i < m; i++) g[e[i][0]].push_back({e[i][1], l[i]}), g[e[i][1]].push_back({e[i][0], l[i]});
  vector<vector<int> > best2(n);
  vector<int> d(n, inf);
  set<pair<int, int> > s;
  for (int i = 0; i < k; i++) s.insert({0, p[i]});
  while (!s.empty())
  {
    int dist = s.begin()->first, u = s.begin()->second;
    s.erase(s.begin());
    if (d[u] != inf) continue;
    d[u] = dist;
    for (const pair<int, int> &v : g[u])
    {
      if (d[v.first] != inf) continue;
      best2[v.first].push_back({d[u] + v.second});
      sort(best2[v.first].begin(), best2[v.first].end());
      if (best2[v.first].size() > 2) best2[v.first].pop_back();
      if (best2[v.first].size() == 2) s.insert({best2[v.first][1], v.first});
    }
  }
  return d[0];
}

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