Submission #1193743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193743		Hamed_Ghaffari	Crocodile's Underground City (IOI11_crocodile)	C++20	89 / 100	2098 ms	168664 KiB

crocodile

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

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 1e5+5;
const int inf = 1e9;

vector<pii> g[MXN];
int dis[MXN];
bool mark[MXN];
set<pii> st[MXN];
priority_queue<pii> pq;

inline void add(int v) {
  if(st[v].size()>=2) pq.push({-next(st[v].begin())->X, v});
}

inline void upd(int v, int d) {
  for(auto [u, w] : g[v])
    st[u].erase({dis[v]+w, v});
  dis[v] = d;
  for(auto [u, w] : g[v])
    st[u].insert({dis[v]+w, v}),
    add(u);
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  for(int i=0; i<M; i++) {
    g[R[i][0]].push_back({R[i][1], L[i]});
    g[R[i][1]].push_back({R[i][0], L[i]});
  }
  for(int i=0; i<N; i++) upd(i, inf);
  for(int i=0; i<K; i++) upd(P[i], 0), mark[P[i]] = 1;
  while(!pq.empty()) {
    int d = -pq.top().X;
    int v = pq.top().Y;
    pq.pop();
    if(mark[v]) continue;
    upd(v, d);
    mark[v] = 1;
  }
  return dis[0];
}

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