Submission #1283527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283527		Faisal_Saqib	Exhibition (JOI19_ho_t2)	C++20	Compilation error	0 ms	0 KiB

joi2019_ho_t2

#include "crocodile.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int QK=1e5+100,inf=1e9;
int n,k;
ll dist[QK],sp[QK];
ll dp[QK][5];
bool vis[QK];
vector<pair<int,int>> adj[QK];
void dykstra(){
  for(int i=0;i<=n;i++)
  {
    dp[i][0]=inf;
    dp[i][1]=inf;
    dist[i]=inf;
  }
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
  for(int j=0;j<k;j++){
    dist[sp[j]]=0;
    pq.push({0,sp[j]});
  }
  while(!pq.empty()){
    auto [d,u]=pq.top();pq.pop();
    if(d>dist[u])continue;
    for(auto [v,w]:adj[u]){
      if(dist[v]>dist[u]+w){
        dist[v]=dist[u]+w;
        pq.push({dist[v],v});
      }
    }
  }
}
void calculate(){
  // dp[u] = answer if we start at u
  // 


  // ord of {(dist,node)}
  // dp[node][0] = min(dist[nei][0])
  // dp[node][1] = 2min(dist[nei][0])
  // vector<pair<ll,int>> ord;
  // for(int i=0;i<n;i++)
  //   ord.push_back({dist[i],i});
  // for(int i=0;i<5;i++)
  // {
  // sort(ord.begin(),ord.end());

  //   for(auto [d,u]:ord){
  //     auto it=lower_bound(sp,sp+k,u);
  //     if(it!=sp+k && *it==u){
  //       dp[u][0]=0;
  //       continue;
  //     }
  //     vector<ll> curp;
  //     for(auto [v,w]:adj[u]){
  //       curp.push_back(dp[v][0]+w);
  //     }
  //     sort(begin(curp),end(curp));
  //     dp[u][0]=min(dp[u][0],curp[1]);
  //   }
  //   ord.clear();
  //   for(int i=0;i<n;i++)
  //   {
  //     ord.push_back({dp[i][0],i});
  //   }
  //   // sort(begin())
  // }
  set<int> cur;
  for(int i=0;i<k;i++)
  {
    dp[sp[i]][0]=0;
    vis[sp[i]]=1;
    for(auto [u,w]:adj[sp[i]])
    {
      if(!vis[u])
      {
        vis[u]=1;
        cur.insert(u);
      }
    }
  }
  while(cur.size())
  {
    set<int> curp;
    vector<pair<ll,ll>> ord;
    for(auto x:cur)
    {
      vector<ll> curp;
      for(auto [v,w]:adj[x]){
        curp.push_back(dp[v][0]+w);
      }
      sort(begin(curp),end(curp));
      dp[x][0]=min(dp[x][0],curp[1]);
      // cout<<"At "<<x<<' '<<dp[x][0]<<endl;;

      ord.push_back({dp[x][0],x});
    }
    sort(begin(ord),end(ord));
    for(auto [asdpo,x]:ord)
    {
      vector<ll> curp;
      for(auto [v,w]:adj[x]){
        curp.push_back(dp[v][0]+w);
      }
      sort(begin(curp),end(curp));
      dp[x][0]=min(dp[x][0],curp[1]);
      ord.push_back({dp[x][0],x});
    }
    for(auto x:cur)
    {
      vis[x]=1;
      for(auto [u,w]:adj[x])
      {
        if(!vis[u])
        {
          vis[u]=1;
          curp.insert(u);
        }
      }
    }
    cur=curp;
  }

}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  n=N,k=K;
  for(int i=0;i<K;i++)
    sp[i]=P[i];
  // sort(sp,sp+K);
  for(int i=0;i<M;i++){
    int u=R[i][0],v=R[i][1],l=L[i];
    adj[u].push_back({v,l});
    adj[v].push_back({u,l});
  }
  dykstra();
  calculate();
  return dp[0][0];
}

Compilation message (stderr)

joi2019_ho_t2.cpp:1:10: fatal error: crocodile.h: No such file or directory
    1 | #include "crocodile.h"
      |          ^~~~~~~~~~~~~
compilation terminated.