Submission #725741

#	Time	Username	Problem	Language	Result	Execution time	Memory
725741		Yell0	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	822 ms	96916 KiB

crocodile

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;

int travel_plan(int N,int M,int R[][2],int L[],int K,int P[]) {
  vector<vector<pli>> gr(N);
  for(int i=0;i<M;++i) {
    gr[R[i][0]].push_back({L[i],R[i][1]});
    gr[R[i][1]].push_back({L[i],R[i][0]});
  }
  vector<bool> vis(N);
  priority_queue<pli,vector<pli>,greater<pli>> pq;
  vector<vector<ll>> dist(N);
  for(int i=0;i<K;++i) {
    vis[P[i]]=1;
    dist[P[i]].push_back(0);
    for(pli p:gr[P[i]]) {
      ll ed=p.first;
      int v=p.second;
      pq.push({ed,v});
    }
  }
  while(!pq.empty()) {
    ll d=pq.top().first;
    int u=pq.top().second;
    dist[u].push_back(d);
    pq.pop();
    if(dist[u].size()<2||vis[u]) continue;
    vis[u]=1;
    for(pli p:gr[u]) {
      int v=p.second;
      ll ed=p.first;
      if(vis[v]) continue;
      pq.push({ed+dist[u][1],v});
    }
  }
  return dist[0][1];
}

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