oj.uz

Submission #872315

# Submission time Handle Problem Language Result Execution time Memory
872315 2023-11-12T18:32:07 Z AkibAzmain Cyberland (APIO23_cyberland) C++17
100 / 100
 2701 ms 66396 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

double
solve (int n, int m, int k, int h,
       std::vector<int> x, std::vector<int> y, std::vector<int> c,
       std::vector<int> arr)
{
  vector < vector < pair < int, int > > > adj (n);
  for (int i = 0; i < m; ++i)
    {
      adj[x[i]].push_back ({ c[i], y[i] });
      adj[y[i]].push_back ({ c[i], x[i] });
    }
  priority_queue < pair < ll, int > > q;
  q.push ({ 0ll, 0 });
  vector < ll > sda (n, -1);
  while (q.size ())
    {
      auto x = q.top ();
      q.pop ();
      if (sda[x.second] != -1) continue;
      sda[x.second] = -x.first;
      if (x.second == h) continue;
      for (auto &y : adj[x.second])
        q.push ({ x.first - y.first, y.second });
    }
  if (sda[h] == -1) return -1;
  set < int > rz;
  rz.insert (0);
  for (int i = 0; i < n; ++i)
    if (arr[i] == 0 && sda[i] > 0)
      rz.insert (i);
  set < int > rd;
  for (int i = 0; i < n; ++i)
    if (arr[i] == 2 && sda[i] > 0)
      rd.insert (i);
  k = min (k, 70);
  vector < vector < double > > da (k + 1, vector < double > (n, -1));
  double ans = 1e18;
  for (ll i = 0; i <= k; ++i)
    {
      priority_queue < pair < double, int > > pq;
      if (!i)
        for (auto &x : rz)
          pq.push ({ (double) 0, x });
      else
        for (auto &x : rd)
          for (auto &y : adj[x])
            pq.push ({ (double) -da[i - 1][x] / 2 - y.first, y.second });
      while (pq.size ())
        {
          auto x = pq.top ();
          pq.pop ();
          if (da[i][x.second] >= -0.5) continue;
          da[i][x.second] = -x.first;
          if (x.second == h) continue;
          for (auto &y : adj[x.second])
            pq.push ({ (double) x.first - y.first, y.second });
        }
      if (da[i][h] >= -0.5)
        ans = min (ans, da[i][h]);
    }
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 344 KB Correct.
2 Correct 29 ms 348 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 844 KB Correct.
2 Correct 37 ms 776 KB Correct.
3 Correct 43 ms 808 KB Correct.
4 Correct 37 ms 852 KB Correct.
5 Correct 37 ms 892 KB Correct.
6 Correct 33 ms 3988 KB Correct.
7 Correct 45 ms 3908 KB Correct.
8 Correct 19 ms 7512 KB Correct.
9 Correct 32 ms 600 KB Correct.
10 Correct 34 ms 600 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 828 KB Correct.
2 Correct 41 ms 852 KB Correct.
3 Correct 43 ms 1120 KB Correct.
4 Correct 37 ms 604 KB Correct.
5 Correct 37 ms 604 KB Correct.
6 Correct 9 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 20960 KB Correct.
2 Correct 217 ms 788 KB Correct.
3 Correct 180 ms 900 KB Correct.
4 Correct 204 ms 816 KB Correct.
5 Correct 98 ms 872 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 772 KB Correct.
2 Correct 33 ms 796 KB Correct.
3 Correct 36 ms 780 KB Correct.
4 Correct 35 ms 3564 KB Correct.
5 Correct 27 ms 604 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 844 KB Correct.
2 Correct 30 ms 880 KB Correct.
3 Correct 32 ms 7768 KB Correct.
4 Correct 24 ms 2940 KB Correct.
5 Correct 30 ms 604 KB Correct.
6 Correct 33 ms 788 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 740 KB Correct.
2 Correct 61 ms 856 KB Correct.
3 Correct 570 ms 23944 KB Correct.
4 Correct 429 ms 6492 KB Correct.
5 Correct 1204 ms 21036 KB Correct.
6 Correct 1179 ms 16576 KB Correct.
7 Correct 441 ms 6340 KB Correct.
8 Correct 351 ms 1504 KB Correct.
9 Correct 290 ms 828 KB Correct.
10 Correct 261 ms 1308 KB Correct.
11 Correct 314 ms 872 KB Correct.
12 Correct 302 ms 836 KB Correct.
13 Correct 328 ms 868 KB Correct.
14 Correct 421 ms 7804 KB Correct.
15 Correct 397 ms 2328 KB Correct.
16 Correct 307 ms 972 KB Correct.
17 Correct 349 ms 924 KB Correct.
18 Correct 317 ms 936 KB Correct.
19 Correct 585 ms 856 KB Correct.
20 Correct 14 ms 348 KB Correct.
21 Correct 19 ms 804 KB Correct.
22 Correct 105 ms 2140 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 1208 KB Correct.
2 Correct 138 ms 1112 KB Correct.
3 Correct 240 ms 66396 KB Correct.
4 Correct 492 ms 2828 KB Correct.
5 Correct 2701 ms 31828 KB Correct.
6 Correct 2552 ms 20972 KB Correct.
7 Correct 834 ms 12948 KB Correct.
8 Correct 444 ms 1452 KB Correct.
9 Correct 631 ms 1428 KB Correct.
10 Correct 569 ms 1060 KB Correct.
11 Correct 257 ms 596 KB Correct.
12 Correct 651 ms 1144 KB Correct.
13 Correct 716 ms 1100 KB Correct.
14 Correct 2330 ms 28392 KB Correct.
15 Correct 1403 ms 33220 KB Correct.
16 Correct 724 ms 11412 KB Correct.
17 Correct 509 ms 2952 KB Correct.
18 Correct 657 ms 1200 KB Correct.
19 Correct 748 ms 1232 KB Correct.
20 Correct 693 ms 1312 KB Correct.
21 Correct 1282 ms 1456 KB Correct.
22 Correct 20 ms 348 KB Correct.
23 Correct 40 ms 780 KB Correct.
24 Correct 235 ms 2428 KB Correct.