Submission #1184687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184687		peteza	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	287 ms	56688 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int inf = 1100000000;

int dist[100005];
int sz[100005];
vector<pii> adj[100005];
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++) {
    adj[R[i][0]].emplace_back(R[i][1], L[i]);
    adj[R[i][1]].emplace_back(R[i][0], L[i]);
  }
  for(int i=0;i<K;i++) {
    sz[P[i]] = 1;
    pq.emplace(0, P[i]);
  }
  while(!pq.empty()) {
    auto e = pq.top(); pq.pop();
    if(sz[e.second] == 2) continue; //already found the best
    else if(!sz[e.second]) {
      sz[e.second]++;
      //found best but
      continue;
    }
    if(e.second == 0) return e.first;
    dist[e.second] = e.first;
    sz[e.second]++;
    for(auto &E:adj[e.second]) {
      pq.emplace(min(inf, E.second + e.first), E.first);
    }
  }
  return -69;
}

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