Submission #955946

#	Time	Username	Problem	Language	Result	Execution time	Memory
955946		Maaxle	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	614 ms	104480 KiB

crocodile

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

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue

using namespace std;

struct res {
    ll i, sum;  
};
bool operator < (const res& i, const res& j) { return (i.sum > j.sum); }

vector<vector<pair<ll, ll>>> adj;
vector<pair<ll, ll>> memo;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  adj.resize(N);
  memo.resize(N, {((ll) 1 << 60), ((ll) 1 << 60)});
  
  range(i, 0, M) {
      adj[R[i][0]].push_back({R[i][1], L[i]});
      adj[R[i][1]].push_back({R[i][0], L[i]});
  }

  pqueue<res> pq;
  range(i, 0, K) {
      memo[P[i]].first = 0;
      pq.push({P[i], 0});
  }

  res t;
  vector<int> visited (N);
  while (!pq.empty()) {
      t = pq.top(); pq.pop();
      ll sec = memo[t.i].second;
      visited[t.i]++;

      if (t.sum <= memo[t.i].first) {
          memo[t.i].second = memo[t.i].first;
          memo[t.i].first = t.sum;
      }
      else memo[t.i].second = min(memo[t.i].second, t.sum);

      if (sec != memo[t.i].second) {
          for (pair<ll, ll> k : adj[t.i]) {
              if (visited[k.first] < 2) {
                  pq.push({k.first, memo[t.i].second + k.second});
              }
          }
      }
    }
    return memo[0].second;
}

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