Submission #899752

#	Time	Username	Problem	Language	Result	Execution time	Memory
899752		lalig777	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	393 ms	73976 KiB

crocodile

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include "crocodile.h"
using namespace std;
 
typedef long long ll;
const ll INF=1e18+1;
 
int travel_plan(int N, int M, int R[][2], int S[], int K, int P[]){
  vector<vector<pair<int,ll> > > listaAdy(N);
  for (int i=0; i<M; i++){
    listaAdy[R[i][0]].push_back(make_pair(R[i][1], S[i]));
    listaAdy[R[i][1]].push_back(make_pair(R[i][0], S[i]));
  }
  vector<pair<ll,ll> > dist(N, make_pair(INF, INF));
  priority_queue<pair<ll, int> >pq;
  for (int i=0; i<K; i++){
    dist[P[i]].first=0;
    dist[P[i]].second=0;
    pq.push(make_pair(0, P[i]));
  }
  while (!pq.empty()){
    int u=pq.top().second;
    ll d=-pq.top().first;
    pq.pop();
    if (dist[u].second<d) continue;
    if (dist[u].first<=d) dist[u].second=d;
    else{
      dist[u].second=dist[u].first;
      dist[u].first=d;
    }
    if (dist[u].second==INF) continue;
    for (auto vec: listaAdy[u]){
      int v=vec.first;
      ll c=vec.second;
      ll dact=dist[u].second+c;
      if(dist[v].second>dact){
        if (dist[v].second==dist[v].first){
          dist[v].first=dact;
          continue;
        }
        dist[v].second=dact;
        if (dist[v].second<dist[v].first){
          dist[v].second=dist[v].first;
          dist[v].first=dact;
        }pq.push(make_pair(-dist[v].second, v));
      }
    }
  }
  if (dist[0].second==INF) return -1;
  return dist[0].second;
}

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