Submission #1174998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174998		achinhchin	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	473 ms	84076 KiB

crocodile

#include "crocodile.h"
#include <algorithm>
#include <vector>
#include <queue>
#include <utility> 
#include <climits>
#include "iostream"

using namespace std;
typedef long long ll;
#define f first
#define s second

vector<pair<ll, ll> > a[100000]; priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > b; ll c[100000], i, t, t2;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  while (M--) a[R[M][0]].push_back(make_pair(L[M], R[M][1])), a[R[M][1]].push_back(make_pair(L[M], R[M][0]));
  while (N--) c[N] = -1; while (K--) c[P[K]] = -2, b.push(make_pair(0, P[K]));
  while (!b.empty()) {
    t = b.top().s, t2 = b.top().f, b.pop();
    if (c[t] > -2) {
      if (c[t] == -1) c[t]--; 
      continue;
    }c[t] = t2;
    for (auto i: a[t]) if (c[i.s] < 0) b.push(make_pair(c[t] + i.f, i.s));
  }return c[0];
}

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