Submission #1140891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140891		0x34c	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	325 ms	73776 KiB

crocodile

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pil pair<int, ll>
#define plii pair<ll, pii>
#define pli pair<ll, int>
#include "crocodile.h"

using namespace std;

const ll INF = 1e15;

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

  vector<vector<ll>> dist(N, vector<ll>(2, INF));
  priority_queue<pli, vector<pli>, greater<pli>> q;

  for (int i = 0; i < K; i++)
  {
    dist[P[i]][0] = dist[P[i]][1] = 0;
    q.push({0, P[i]});
  }

  while (!q.empty())
  {
    ll w;
    int v;
    tie(w, v) = q.top();
    q.pop();

    if (dist[v][1] < w)
      continue;

    for (pil e : graph[v])
    {
      ll wei;
      int u;
      tie(u, wei) = e;

      if (dist[u][1] <= w + wei)
        continue;

      if (dist[u][0] > w + wei)
      {
        if (dist[u][0] < dist[u][1])
          q.push({dist[u][0], u});

        dist[u][1] = dist[u][0];
        dist[u][0] = w + wei;
      }
      else if (dist[u][1] > w + wei)
      {
        dist[u][1] = w + wei;
        q.push({w + wei, u});
      }
    }
  }

  return dist[0][1];
}

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