Submission #672185

#	Time	Username	Problem	Language	Result	Execution time	Memory
672185		ThegeekKnight16	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	974 ms	102608 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const ll MAXN = 1e5 + 10;
vector<ll> grafo[MAXN], pesos[MAXN];
bool Marc[MAXN];
ll Dist[MAXN], Dist2[MAXN];
vector<ll> process;

void dijkstra(ll N) {
  set<pair<ll, ll> > fora;

  for (ll i = 0; i < N; i++)
    {
        //fora.emplace(INF, i);
        Dist[i] = Dist2[i] = INF;
    }

  for (auto p : process)
  {
    Dist[p] = Dist2[p] = 0;
    fora.emplace(0, p);
  }

  while (!fora.empty())
  {
    ll cur = fora.begin()->second;
    fora.erase(fora.begin());
    if (Marc[cur])
      continue;
    Marc[cur] = 1;
    // cerr << fora.size() << '\n';
    for (ll i = 0; i < grafo[cur].size(); i++) {
      ll viz = grafo[cur][i];
      ll p = pesos[cur][i];

      if (Dist2[cur] + p < Dist[viz])
      {
        Dist2[viz] = Dist[viz];
        Dist[viz] = Dist2[cur] + p;
        fora.emplace(Dist2[viz], viz);
      }
      else if (Dist2[cur] + p < Dist2[viz])
      {
        Dist2[viz] = Dist2[cur] + p;
        fora.emplace(Dist2[viz], viz);
      }
    }
  }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  for (ll i = 0; i < M; i++) {
    ll X = R[i][0];
    ll Y = R[i][1];
    ll P = L[i];

    grafo[X].push_back(Y);
    pesos[X].push_back(P);
    grafo[Y].push_back(X);
    pesos[Y].push_back(P);
  }

  for (int k = 0; k < K; k++)
    process.push_back(P[k]);

  dijkstra(N);

  return Dist2[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'void dijkstra(long long int)':
crocodile.cpp:35:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (ll i = 0; i < grafo[cur].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~

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