oj.uz

Submission #872314

# Submission time Handle Problem Language Result Execution time Memory
872314 2023-11-12T18:22:32 Z AkibAzmain Cyberland (APIO23_cyberland) C++17
100 / 100
 2990 ms 74068 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, 80);
  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 23 ms 604 KB Correct.
2 Correct 22 ms 512 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 900 KB Correct.
2 Correct 41 ms 760 KB Correct.
3 Correct 39 ms 940 KB Correct.
4 Correct 37 ms 852 KB Correct.
5 Correct 37 ms 812 KB Correct.
6 Correct 32 ms 3988 KB Correct.
7 Correct 52 ms 3896 KB Correct.
8 Correct 19 ms 7516 KB Correct.
9 Correct 31 ms 604 KB Correct.
10 Correct 31 ms 600 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 840 KB Correct.
2 Correct 40 ms 896 KB Correct.
3 Correct 38 ms 1052 KB Correct.
4 Correct 37 ms 604 KB Correct.
5 Correct 38 ms 860 KB Correct.
6 Correct 9 ms 3672 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 20884 KB Correct.
2 Correct 209 ms 792 KB Correct.
3 Correct 181 ms 924 KB Correct.
4 Correct 196 ms 768 KB Correct.
5 Correct 95 ms 624 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 780 KB Correct.
2 Correct 32 ms 796 KB Correct.
3 Correct 33 ms 776 KB Correct.
4 Correct 40 ms 3564 KB Correct.
5 Correct 25 ms 600 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 872 KB Correct.
2 Correct 30 ms 848 KB Correct.
3 Correct 36 ms 7816 KB Correct.
4 Correct 24 ms 3020 KB Correct.
5 Correct 30 ms 644 KB Correct.
6 Correct 33 ms 804 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 812 KB Correct.
2 Correct 61 ms 856 KB Correct.
3 Correct 590 ms 23964 KB Correct.
4 Correct 418 ms 6652 KB Correct.
5 Correct 1190 ms 20900 KB Correct.
6 Correct 1173 ms 16268 KB Correct.
7 Correct 422 ms 6344 KB Correct.
8 Correct 350 ms 1596 KB Correct.
9 Correct 305 ms 848 KB Correct.
10 Correct 261 ms 804 KB Correct.
11 Correct 309 ms 852 KB Correct.
12 Correct 303 ms 824 KB Correct.
13 Correct 330 ms 836 KB Correct.
14 Correct 410 ms 7880 KB Correct.
15 Correct 402 ms 2392 KB Correct.
16 Correct 303 ms 788 KB Correct.
17 Correct 343 ms 880 KB Correct.
18 Correct 315 ms 848 KB Correct.
19 Correct 592 ms 856 KB Correct.
20 Correct 12 ms 536 KB Correct.
21 Correct 19 ms 600 KB Correct.
22 Correct 112 ms 2200 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 1224 KB Correct.
2 Correct 152 ms 1116 KB Correct.
3 Correct 268 ms 74068 KB Correct.
4 Correct 513 ms 3284 KB Correct.
5 Correct 2990 ms 34952 KB Correct.
6 Correct 2924 ms 22156 KB Correct.
7 Correct 932 ms 15124 KB Correct.
8 Correct 469 ms 3204 KB Correct.
9 Correct 715 ms 2104 KB Correct.
10 Correct 631 ms 1948 KB Correct.
11 Correct 275 ms 1876 KB Correct.
12 Correct 735 ms 2224 KB Correct.
13 Correct 813 ms 2272 KB Correct.
14 Correct 2663 ms 33060 KB Correct.
15 Correct 1567 ms 39164 KB Correct.
16 Correct 767 ms 12852 KB Correct.
17 Correct 532 ms 5064 KB Correct.
18 Correct 758 ms 2212 KB Correct.
19 Correct 850 ms 2280 KB Correct.
20 Correct 774 ms 2084 KB Correct.
21 Correct 1461 ms 3252 KB Correct.
22 Correct 22 ms 604 KB Correct.
23 Correct 45 ms 860 KB Correct.
24 Correct 268 ms 2624 KB Correct.