Submission #118245

#	Time	Username	Problem	Language	Result	Execution time	Memory
118245		MAMBA	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1414 ms	86500 KiB

crocodile

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

using namespace std;

inline void read() {}
template <class S>
inline void read(S &arg) {
  cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
  while (Lptr != Rptr) {
    read(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
  read(arg);
  read(rest...);
}

inline void write() {}
template <class S>
inline void write(S arg) {
  cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char C_ = ' ') {
  if (Lptr != Rptr) {
    write(*Lptr);
    Lptr++;
  }
  while (Lptr != Rptr) {
    write(C_);
    write(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void write(S arg, T... rest) {
  write(arg);
  write(' ');
  write(rest...);
}

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

template <class T, class S>
inline bool smin(T &a, S b) {
  return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
  return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 1e9 + 7;
constexpr int N = 1e6 + 10;

template <typename T>
inline T mod(T &v) {
  return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
  return mod(l += r);
}

ll po(ll v, ll u) {
  return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}

pll dist[N];
set<pair<pll, int>> st;
vi adj[N];

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
  rep(i, 0, m) {
    adj[R[i][0]].pb(i);
    adj[R[i][1]].pb(i);
  }
  memset(dist, 63, sizeof(dist));
  rep(i, 0, k) {
    dist[P[i]] = {0, 0};
    st.insert({dist[P[i]], P[i]});
  }
  while (st.size()) {
    int v = st.begin()->second;
    st.erase(st.begin());
    for (auto e : adj[v]) {
      ll exp = dist[v].first + L[e];
      int u = R[e][0] ^ R[e][1] ^ v;
      pll nd = dist[u];
      if (exp <= nd.second) {
        nd.first = nd.second;
        nd.second = exp;
      } else if (exp < nd.first)
        nd.first = exp;
      if (nd != dist[u]) {
        st.erase({dist[u], u});
        dist[u] = nd;
        st.insert({dist[u], u});
      }
    }
  }
  return dist[0].first;
}

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