oj.uz

Submission #756073

# Submission time Handle Problem Language Result Execution time Memory
756073 2023-06-11T04:05:24 Z asdfgrace Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 0 ms 212 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  vector<vector<pair<int, i64>>> edges(N);
  for (int i = 0; i < M; ++i) {
    edges[R[i][1]].emplace_back(R[i][0], i64(L[i]));
    edges[R[i][0]].emplace_back(R[i][1], i64(L[i]));
  }
  vector<vector<int>> sp_edges(N);
  vector<bool> visited(N, false);
  vector<i64> sp1(N, 1e18);
  priority_queue<array<i64, 3>> q;
  for (int i = 0; i < K; ++i) {
    sp1[P[i]] = 0;
    q.push({0, P[i], P[i]});
  }
  while (!q.empty()) {
    i64 dist = -q.top()[0], node = q.top()[1], prev = q.top()[2];
    q.pop();
    if (node != prev && dist == sp1[node]) sp_edges[node].push_back(prev);
    if (visited[node]) continue;
    visited[node] = true;
    if (node == 0) continue;
    for (auto [next, weight] : edges[node]) {
      if (dist + weight <= sp1[next]) {
        sp1[next] = dist + weight;
        q.push({-sp1[next], next, node});
      }
    }
  }
  fill(visited.begin(), visited.end(), false);
  vector<i64> sp2(N, 1e18);
  q.push({0, 0, 0});
  while (!q.empty()) {
    i64 dist = -q.top()[0], node = q.top()[1], prev = q.top()[2];
    q.pop();
    if (visited[node]) continue;
    visited[node] = true;
    for (auto [next, weight] : edges[node]) {
      if (sp_edges[node].size() == 1 && next == sp_edges[node][0]) continue;
      if (dist + weight <= sp2[next]) {
        sp2[next] = dist + weight;
        q.push({-sp2[next], next, node});
      }
    }
  }
  i64 ans = 1e18;
  for (int i = 0; i < K; ++i) {
    ans = min(ans, sp2[P[i]]);
  }
  return int(ans);
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:38:48: warning: unused variable 'prev' [-Wunused-variable]
   38 |     i64 dist = -q.top()[0], node = q.top()[1], prev = q.top()[2];
      |                                                ^~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -