oj.uz

Submission #672185

# Submission time Handle Problem Language Result Execution time Memory
672185 2022-12-15T00:54:34 Z ThegeekKnight16 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 974 ms 102608 KB 
#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

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5160 KB Output is correct
12 Correct 7 ms 5716 KB Output is correct
13 Correct 6 ms 5844 KB Output is correct
14 Correct 3 ms 5016 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5160 KB Output is correct
12 Correct 7 ms 5716 KB Output is correct
13 Correct 6 ms 5844 KB Output is correct
14 Correct 3 ms 5016 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 614 ms 88972 KB Output is correct
17 Correct 119 ms 27852 KB Output is correct
18 Correct 155 ms 29556 KB Output is correct
19 Correct 974 ms 102608 KB Output is correct
20 Correct 279 ms 74088 KB Output is correct
21 Correct 53 ms 14484 KB Output is correct
22 Correct 372 ms 68920 KB Output is correct