oj.uz

Submission #890954

# Submission time Handle Problem Language Result Execution time Memory
890954 2023-12-22T05:35:36 Z NeroZein Cyberland (APIO23_cyberland) C++17
100 / 100
 1505 ms 101968 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std; 

using key = pair<double, int>; 

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
  K = min(K, 100); 
  vector<vector<pair<int, int>>> g(N);
  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]); 
  }
  vector<bool> reachable(N, 0);
  function<void(int)> dfs = [&](int v) {
    if (reachable[v]) return;
    reachable[v] = true;
    if (v == H) return;
    for (auto [u, _] : g[v]) {
      dfs(u); 
    }
  };
  dfs(0);
  priority_queue<key, vector<key>, greater<key>> pq;
  vector<vector<double>> dp(N, vector<double> (K + 2, -1)); 
  for (int k = 0; k <= K; ++k) {
    for (int i = 0; i < N; ++i) {
      if (i == 0 || (reachable[i] && arr[i] == 0)) {
        dp[i][k] = 0; 
      }
      if (dp[i][k] != -1) {
        pq.emplace(dp[i][k], i); 
      }
    }
    while (!pq.empty()) {
      auto [cost, v] = pq.top();
      pq.pop(); 
      if (cost != dp[v][k] || v == H) {
        continue; 
      }
      for (auto [u, w] : g[v]) {
        double nc = cost + w; 
        if (dp[u][k] == -1 || nc < dp[u][k]) {
          dp[u][k] = nc;
          pq.emplace(dp[u][k], u);
        }
        if (arr[u] == 2) {
          nc = nc / 2.0; 
          if (dp[u][k + 1] == -1 || nc < dp[u][k + 1]) {
            dp[u][k + 1] = nc;
          }
        }
      }
    }
  }
  double ans = -1; 
  for (int i = 0; i <= K; ++i) {
    if (dp[H][i] != -1 && (ans == -1 || ans > dp[H][i])) {
      ans = dp[H][i];
    }
  }
  if (reachable[H]) assert(ans != -1);
  else assert(ans == -1); 
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 600 KB Correct.
2 Correct 22 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 868 KB Correct.
2 Correct 106 ms 852 KB Correct.
3 Correct 101 ms 852 KB Correct.
4 Correct 119 ms 996 KB Correct.
5 Correct 104 ms 1068 KB Correct.
6 Correct 150 ms 4220 KB Correct.
7 Correct 202 ms 4136 KB Correct.
8 Correct 97 ms 7772 KB Correct.
9 Correct 58 ms 348 KB Correct.
10 Correct 58 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 828 KB Correct.
2 Correct 134 ms 1596 KB Correct.
3 Correct 122 ms 1784 KB Correct.
4 Correct 68 ms 1364 KB Correct.
5 Correct 68 ms 1364 KB Correct.
6 Correct 40 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 23388 KB Correct.
2 Correct 88 ms 1920 KB Correct.
3 Correct 75 ms 1828 KB Correct.
4 Correct 81 ms 1748 KB Correct.
5 Correct 52 ms 1360 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 868 KB Correct.
2 Correct 69 ms 600 KB Correct.
3 Correct 80 ms 824 KB Correct.
4 Correct 123 ms 3924 KB Correct.
5 Correct 40 ms 532 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 848 KB Correct.
2 Correct 60 ms 1736 KB Correct.
3 Correct 57 ms 31164 KB Correct.
4 Correct 72 ms 3496 KB Correct.
5 Correct 48 ms 1364 KB Correct.
6 Correct 77 ms 1832 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 796 KB Correct.
2 Correct 15 ms 1116 KB Correct.
3 Correct 593 ms 29520 KB Correct.
4 Correct 241 ms 9160 KB Correct.
5 Correct 356 ms 19916 KB Correct.
6 Correct 143 ms 9948 KB Correct.
7 Correct 241 ms 8476 KB Correct.
8 Correct 193 ms 3184 KB Correct.
9 Correct 77 ms 1776 KB Correct.
10 Correct 78 ms 1748 KB Correct.
11 Correct 164 ms 2572 KB Correct.
12 Correct 90 ms 1820 KB Correct.
13 Correct 83 ms 1892 KB Correct.
14 Correct 233 ms 11536 KB Correct.
15 Correct 213 ms 4616 KB Correct.
16 Correct 80 ms 1892 KB Correct.
17 Correct 108 ms 1956 KB Correct.
18 Correct 94 ms 1816 KB Correct.
19 Correct 290 ms 2760 KB Correct.
20 Correct 5 ms 604 KB Correct.
21 Correct 7 ms 732 KB Correct.
22 Correct 12 ms 1372 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 1348 KB Correct.
2 Correct 39 ms 1884 KB Correct.
3 Correct 443 ms 101968 KB Correct.
4 Correct 295 ms 5552 KB Correct.
5 Correct 1131 ms 39352 KB Correct.
6 Correct 445 ms 15660 KB Correct.
7 Correct 633 ms 19444 KB Correct.
8 Correct 260 ms 3232 KB Correct.
9 Correct 185 ms 2380 KB Correct.
10 Correct 191 ms 2096 KB Correct.
11 Correct 129 ms 1684 KB Correct.
12 Correct 209 ms 2432 KB Correct.
13 Correct 191 ms 2348 KB Correct.
14 Correct 1505 ms 40396 KB Correct.
15 Correct 1238 ms 48676 KB Correct.
16 Correct 420 ms 13196 KB Correct.
17 Correct 309 ms 5572 KB Correct.
18 Correct 181 ms 2396 KB Correct.
19 Correct 243 ms 2356 KB Correct.
20 Correct 222 ms 2360 KB Correct.
21 Correct 852 ms 3176 KB Correct.
22 Correct 10 ms 640 KB Correct.
23 Correct 14 ms 1136 KB Correct.
24 Correct 33 ms 1884 KB Correct.