Submission #986817

#	Time	Username	Problem	Language	Result	Execution time	Memory
986817		huutuan	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	441 ms	96580 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e5+10, inf=1e18;
int n, m, vis[N];
pair<int, int> f[N][2];
vector<pair<int, int>> g[N];

void optimize(int i, pair<int, int> x){
   if (x.second==f[i][0].second || x.second==f[i][1].second){
      if (x.second==f[i][0].second) f[i][0].first=min(f[i][0].first, x.first);
      else f[i][1].first=min(f[i][1].first, x.first);
      if (f[i][0]>f[i][1]) swap(f[i][0], f[i][1]);
      return;
   }
   if (x<f[i][0]) f[i][1]=f[i][0], f[i][0]=x;
   else f[i][1]=min(f[i][1], x);
}

int32_t travel_plan(int32_t _N, int32_t M, int32_t R[][2], int32_t L[], int32_t K, int32_t P[])
{
   n=_N, m=M;
   for (int i=0; i<m; ++i){
      int u=R[i][0]+1, v=R[i][1]+1, w=L[i];
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
   }
   for (int i=1; i<=n; ++i) f[i][0]=f[i][1]={inf, -1};
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   for (int i=0; i<K; ++i){
      int u=P[i]+1;
      f[u][0]=f[u][1]={0, u};
      pq.emplace(0, u);
   }
   while (pq.size()){
      int u=pq.top().second; pq.pop();
      if (vis[u]) continue;
      vis[u]=1;
      for (auto &e:g[u]){
         int v=e.first, w=e.second;
         pair<int, int> tmp[2]={f[v][0], f[v][1]};
         optimize(v, {f[u][1].first+w, u});
         if (tmp[0]!=f[v][0] || tmp[1]!=f[v][1]) pq.emplace(f[v][1].first, v);
      }
   }
   return f[1][1].first;
}

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