oj.uz

Submission #871823

# Submission time Handle Problem Language Result Execution time Memory
871823 2023-11-11T16:19:28 Z vjudge1 Cyberland (APIO23_cyberland) C++17
21 / 100
 40 ms 7816 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] });
    }
  if (n <= 3)
    {
      vector < double > da (n, -1);
      auto dfs = [&] (auto self, int v, int p, double d) -> void
      {
        if (arr[v] == 0) d = 0;
        if (arr[v] == 2) d /= 2;
        bool stop = false;
        if (da[v] >= 0) stop = true;
        da[v] = d;
        if (stop) return;
        for (auto &x : adj[v])
          if (x.second != p)
            self (self, x.second, v, d + x.first);
      };
      dfs (dfs, 0, -1, 0);
      return da[h];
    }
  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 15 ms 608 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 604 KB Correct.
2 Correct 34 ms 592 KB Correct.
3 Correct 31 ms 604 KB Correct.
4 Correct 32 ms 604 KB Correct.
5 Correct 38 ms 572 KB Correct.
6 Correct 28 ms 1556 KB Correct.
7 Correct 39 ms 1440 KB Correct.
8 Correct 16 ms 2768 KB Correct.
9 Correct 28 ms 348 KB Correct.
10 Correct 28 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 604 KB Correct.
2 Correct 34 ms 600 KB Correct.
3 Correct 33 ms 604 KB Correct.
4 Correct 31 ms 344 KB Correct.
5 Correct 33 ms 348 KB Correct.
6 Correct 7 ms 1372 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 600 KB Correct.
2 Correct 30 ms 600 KB Correct.
3 Correct 36 ms 604 KB Correct.
4 Correct 32 ms 1368 KB Correct.
5 Incorrect 24 ms 348 KB Wrong Answer.
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 604 KB Correct.
2 Correct 27 ms 604 KB Correct.
3 Correct 31 ms 7816 KB Correct.
4 Correct 20 ms 1208 KB Correct.
5 Incorrect 28 ms 348 KB Wrong Answer.
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 600 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 568 KB Wrong Answer.
2 Halted 0 ms 0 KB -