Submission #955367

#	Time	Username	Problem	Language	Result	Execution time	Memory
955367		blackslex	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	444 ms	91068 KiB

crocodile

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

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

ll n, m, k;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  n = N; m = M; k = K;
  vector<vector<pii>> v(n, vector<pii>());
  for (int i = 0; i < m; i++) v[R[i][0]].emplace_back(R[i][1], L[i]), v[R[i][1]].emplace_back(R[i][0], L[i]);
  for (int i = 0; i < n; i++) sort(v[i].begin(), v[i].end(), [&] (const pii &p1, const pii &p2) {
    return p1.second < p2.second;
  });
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  vector<pii> d(n, pii(1e18, 1e18));
  vector<bool> f(n);
  for (int i = 0; i < k; i++) d[P[i]] = pii(0, 0), pq.emplace(0, P[i]);
  while (!pq.empty()) {
    auto [nd, nn] = pq.top(); pq.pop();
    if (f[nn]) continue; f[nn] = 1;
    for (auto &[tn, td]: v[nn]) {
      if (d[tn].second > d[nn].second + td) {
        d[tn].second = d[nn].second + td;
        if (d[tn].second < d[tn].first) swap(d[tn].second, d[tn].first);
        if (d[tn].second != 1e18) pq.emplace(d[tn].second, tn);
      }
    }
  }
  return d[0].second;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:23:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |     if (f[nn]) continue; f[nn] = 1;
      |     ^~
crocodile.cpp:23:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |     if (f[nn]) continue; f[nn] = 1;
      |                          ^

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