Submission #718159

#	Time	Username	Problem	Language	Result	Execution time	Memory
718159		thimote75	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	671 ms	74336 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>

using namespace std;

#define t_road pair<int, num>
#define t_roads vector<t_road>
#define graph vector<t_roads>
#define num long long
#define next first
#define cost second
#define ndata vector<num>
#define inf 1e18
#define ni pair<num, int>
#define pq set<ni>

graph roads;
ndata t_max;
ndata t_mix;

pq update_queue;

bool _update (int index, num value) {
  if (t_max[index] >= value) {
    t_mix[index] = t_max[index];
    t_max[index] = value;
  } else if (t_mix[index] > value) {
    t_mix[index] = value;
  } else return false;

  return t_mix[index] != inf;
}
void update (int index, num value) {
  ni data = { t_mix[index], index };

  if (_update(index, value)) {
    if (update_queue.find(data) != update_queue.end())
      update_queue.erase(data);
    
    update_queue.insert({ t_mix[index], index });
  }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  roads.resize(N);
  t_max.resize(N, inf);
  t_mix.resize(N, inf);

  for (int iR = 0; iR < M; iR ++) {
    int a = R[iR][0];
    int b = R[iR][1];
    int c = L[iR];

    roads[a].push_back({ b, c });
    roads[b].push_back({ a, c });
  }

  for (int i = 0; i < K; i ++) {
    update(P[i], 0);
    update(P[i], 0);
  }

  while (update_queue.size() != 0) {
    ni position = *update_queue.begin();
    update_queue.erase(position);
    
    int current = position.second;
    num time    = position.first;
    if (current == 0) return time;

    for (t_road next_road : roads[current]) {
      num next_time = next_road.cost + time;
      int next_node = next_road.next;

      update(next_node, next_time);
    }
  }

  return N;
}

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