Submission #494323

#	Time	Username	Problem	Language	Result	Execution time	Memory
494323		keertan	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	611 ms	46828 KiB

crocodile

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

#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
#define sz(x) (int)(x.size())
const int N=1e4+5,N1=2e9,mod=1e9+7;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  int n,m,k;
  n=N;
  m=M;
  k=K;
 
  using gh=pair<int,int>;
  vector<pair<int,int>> adj[n];
  for (int i=0,u,v,w;i<m;i++){
    u=R[i][0],v=R[i][1],w=L[i];
    adj[u].emplace_back(v,w);
    adj[v].emplace_back(u,w);
  }
  vector<gh> dis(n,{N1,N1});
  priority_queue<gh,vector<gh>,greater<gh>> q;
  vector<bool> vis(n);
  for (int i=0,x;i<k;i++){
    x=P[i];
    q.emplace(0,x);
    dis[x]={0,0};
  }
  while(!q.empty()){
    int u,dis1;
    tie(dis1,u)=q.top();
    q.pop();
    //cerr<<u<<" "<<dis1<<"\n";
    if (vis[u]){continue;}
    vis[u]=1;
    for (const gh &it:adj[u]){
      int cur=dis1+it.second;
      if (dis[it.first].first>=cur){
        dis[it.first].second=dis[it.first].first;
        dis[it.first].first=cur;
      }
      else if (cur<dis[it.first].second){
        dis[it.first].second=cur;
      }
      if (dis[it.first].first!=N1 && dis[it.first].second!=N1 && !vis[it.first]){
        q.emplace(dis[it.first].second,it.first);
      }
    }
  }
  
  return dis[0].second;
}

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