oj.uz

Submission #297786

# Submission time Handle Problem Language Result Execution time Memory
297786 2020-09-11T22:41:30 Z Haunted_Cpp Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2 ms 2688 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
const int MAX_N = 1e5 + 5;

vector<vector<pair<int, int>>> g(MAX_N);
bitset<MAX_N> is_exit;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  for (int i = 0; i < M; i++) {
    g[R[i][0]].emplace_back(R[i][1], L[i]);
    g[R[i][1]].emplace_back(R[i][0], L[i]);
  }
  for (int i = 0; i < K; i++) {
    is_exit[P[i]] = 1;
  }
  
  priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
  vector<i64> closest_one(N, 1e18);
  for (int i = 0; i < K; i++) {
    closest_one[P[i]] = 0;
    pq.emplace(closest_one[P[i]], P[i]);
  }
  while(!pq.empty()) {
    auto [w, node] = pq.top();
    pq.pop();
    if (w != closest_one[node]) {
      continue;
    }
    for (auto [to, cost] : g[node]) {
      if (closest_one[to] > closest_one[node] + cost) {
        closest_one[to] = closest_one[node] + cost;
        pq.emplace(closest_one[to], to);
      }
    }
  }
  
  auto Dijkstra = [&](int is_blocked) {
    vector<i64> dist(N, 1e18);
    priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
    dist[0] = 0;
    pq.emplace(dist[0], 0);
    while(!pq.empty()) {
      auto [w, node] = pq.top();
      pq.pop();
      if (w != dist[node]) {
        continue;
      }
      bool type = false;
      for (auto [to, cost] : g[node]) {
        if (to == is_blocked) {
          type = true;
        }
      }
      pair<i64, int> blocked = {1e18, 1e9};
      for (auto [to, cost] : g[node]) {
        blocked = min(blocked, {closest_one[to] + cost , to});
      }
      for (auto [to, cost] : g[node]) {
        if (type) {
          if (to == is_blocked) {
            continue;
          }
        } else {
          if (to == blocked.second) {
            continue;
          }
        }
        if (dist[to] > dist[node] + cost) {
          dist[to] = dist[node] + cost;
          pq.emplace(dist[to], to);
        }
      }
    }
    i64 mn = 1e18;
    for (int i = 0; i < N; i++) {
      if (is_exit[i] && is_blocked != i) {
        mn = min(mn, dist[i]);
      }
    }
    return mn;
  };
  
  i64 best_way = 0;
  for (int i = 0; i < K; i++) {
    best_way = max(best_way, Dijkstra(P[i]));
  }
  return best_way;
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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