oj.uz

Submission #871765

# Submission time Handle Problem Language Result Execution time Memory
871765 2023-11-11T13:52:49 Z vjudge1 Cyberland (APIO23_cyberland) C++17
44 / 100
 40 ms 9812 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);
  vector < ll > eda (n, -1);
  q.push ({ 0ll, h });
  while (q.size ())
    {
      auto x = q.top ();
      q.pop ();
      if (eda[x.second] != -1) continue;
      eda[x.second] = -x.first;
      for (auto &y : adj[x.second])
        q.push ({ x.first - y.first, y.second });
    }
  double ans = 1e18;
  for (auto &x : rz) ans = min (ans, (double) eda[x]);
  // vector < ll > dda (n, -1);
  // vector < ll > bfd (n, (ll) 1e18);
  // priority_queue < pair < ll, pair < int, int > > > pq;
  // for (auto &x : rd) pq.insert ({ 0ll, make_pair (x, x) });
  // while (pq.size ())
  //   {
  //     auto x = q.top ();
  //     q.pop ();
  //     if (x.second.first == h) continue;
  //     if (dda[x.second.first] == -1 || dda[x.second.first] == -x.first)
  //       bfd[x.second.second] = min (bfd[x.second.second], -x.first);
  //     if (dda[x.second.first] != -1) continue;
  //     dda[x.second.first] = -x.first;
  //     for (auto &y : adj[x.second.first])
  //       q.push ({ x.first - y.first, make_pair (y.second, x.second.first) });
  //   }
  // for (auto &x : rd)
  //   {
  //     bfd[x]
  //   }
  return ans;
}

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1372 KB Correct.
2 Correct 33 ms 1624 KB Correct.
3 Correct 31 ms 1564 KB Correct.
4 Correct 33 ms 1620 KB Correct.
5 Correct 32 ms 1620 KB Correct.
6 Correct 28 ms 2464 KB Correct.
7 Correct 40 ms 2492 KB Correct.
8 Correct 16 ms 3164 KB Correct.
9 Correct 28 ms 1392 KB Correct.
10 Correct 28 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1620 KB Correct.
2 Correct 36 ms 1484 KB Correct.
3 Correct 31 ms 1576 KB Correct.
4 Correct 31 ms 1368 KB Correct.
5 Correct 33 ms 1280 KB Correct.
6 Correct 7 ms 1628 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1372 KB Correct.
2 Correct 37 ms 1628 KB Correct.
3 Correct 29 ms 1628 KB Correct.
4 Correct 34 ms 2268 KB Correct.
5 Correct 23 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1628 KB Correct.
2 Correct 27 ms 1344 KB Correct.
3 Correct 39 ms 9812 KB Correct.
4 Correct 22 ms 1816 KB Correct.
5 Correct 28 ms 1372 KB Correct.
6 Correct 29 ms 1372 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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