oj.uz

Submission #749794

# Submission time Handle Problem Language Result Execution time Memory
749794 2023-05-28T13:46:30 Z NeroZein Cyberland (APIO23_cyberland) C++17
0 / 100
 2208 ms 21072 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

using T = pair<double, int>;

vector<int> a;
vector<bool> vis; 
vector<int> zeros;
vector<vector<pair<int, int>>> g; 
void Dfs (int v) {
  vis[v] = true;
  if (a[v] == 0) {
    zeros.push_back(v);
  }
  for (auto [u, w] : g[v]) {
    if (!vis[u]) {
      Dfs(u); 
    }
  }
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
  g.resize(N);
  a.resize(N);
  vis.resize(N);
  K = min(K, 90); 
  for (int i = 0; i < M; ++i) {
    g[x[i]].emplace_back(y[i], c[i]); 
    g[y[i]].emplace_back(x[i], c[i]); 
  }
  vis[H] = true; 
  Dfs(0); 
  double ans = 1e18;
  vector<vector<double>> cost(K + 1, vector<double>(N, 1e18)); 
  cost[0][0] = 0;
  for (int i : zeros) {
    cost[0][i] = 0; 
  }
  for (int i = 0; i <= K; ++i) {
    priority_queue<T, vector<T>, greater<T>> pq; 
    for (int j = 0; j < N; ++j) {
      if (cost[i][j] != 1e18) {
        pq.push({cost[i][j], j});
      }
      while (!pq.empty()) {
        auto [c, v] = pq.top();
        pq.pop();
        if (c > cost[i][v]) {
          continue;
        }
        for (auto [u, w] : g[v]) {
          if (arr[u] == 2) {
            if (i < K && (c + w) / 2.0 < cost[i + 1][u]) {
              cost[i + 1][u] = (c + w) / 2.0; 
            }
          }
          if (c + w < cost[i][u]) {
            cost[i][u] = c + w; 
            pq.push({cost[i][u], u});
          }
        }
      }
    }
  }
  for (int i = 0; i <= K; ++i) {
    ans = min(ans, cost[i][H]); 
  }
  return ans == 1e18 ? -1.0 : ans; 
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2208 ms 880 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 21072 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1000 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 1280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -