Submission #192443

#	Time	Username	Problem	Language	Result	Execution time	Memory
192443		kdh9949	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	801 ms	61480 KiB

crocodile

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

using pii = pair<int, int>;
#define x first
#define y second

static const int N = 100000;

int d[N][2], upd[N];
vector<pii> e[N];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
  for(int i = 0; i < m; i++){
    e[R[i][0]].emplace_back(R[i][1], L[i]);
    e[R[i][1]].emplace_back(R[i][0], L[i]);
  }
  
  memset(d, 0x3f, sizeof(d));
  for(int i = 0; i < k; i++){
    d[P[i]][0] = d[P[i]][1] = 0;
    pq.emplace(0, P[i]);
  }

  while(!pq.empty()){
    pii c = pq.top();
    pq.pop();
    if(c.x != d[c.y][1] || upd[c.y]) continue;
    upd[c.y] = 1;
    for(pii i : e[c.y]){
      if(d[i.x][1] > c.x + i.y){
        if(d[i.x][0] >= c.x + i.y){ d[i.x][1] = d[i.x][0]; d[i.x][0] = c.x + i.y; }
        else d[i.x][1] = c.x + i.y;
        pq.emplace(c.x + i.y, i.x);
      }
    }
  }

  return d[0][1];
}

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