Submission #1099134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099134		akamizane	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	368 ms	90244 KiB

crocodile

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

using ll = long long;
using pii = pair<int,long long>;
 
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){if (a < b) {a = b; return true;}return false;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){if (a > b) {a = b; return true;}return false;}
 
ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  int n, m, k;
  n = N, m = M, k = K;
  vector<vector<pair<int,long long>>> ad(n);
  REP(i, m){
    int u, v, w;
    u = R[i][0], v = R[i][1], w = L[i];
    ad[u].pb({v, w});
    ad[v].pb({u, w});
  }
  vector<vector<ll>> d(n, vector<ll> (2, 1e18));
  using T = pair<long long, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  REP(i, k){
    int p;
    p = P[i];
    d[p][0] = d[p][1] = 0;
    pq.push({0, p});
  }
  while(pq.size()){
    auto [val, u] = pq.top();
    pq.pop();
    if (val != d[u][1]) continue;
    for (auto [v, w] : ad[u]){
      if (val + w < d[v][0]){
        if (d[v][0] != d[v][1] && d[v][0] < 1e18){
          d[v][1] = d[v][0];
          pq.push({d[v][1], v});
        }
        d[v][0] = val + w;
      }
      else if (val + w < d[v][1]){
        d[v][1] = val + w;
        pq.push({d[v][1], v});
      }
    }
  }
  return d[0][1];
}

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