oj.uz

Submission #773792

# Submission time Handle Problem Language Result Execution time Memory
773792 2023-07-05T08:37:10 Z peijar Cyberland (APIO23_cyberland) C++17
44 / 100
 452 ms 9204 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const double INF = 1e18;
template <typename T> using min_pq = priority_queue<T, vector<T>, greater<T>>;

double solve(signed nbSommets, signed nbAretes, signed maxDiv, signed arrival,
             vector<signed> x, vector<signed> y, vector<signed> cost,
             vector<signed> effect) {
  vector<vector<pair<int, int>>> adj(nbSommets);
  for (int i = 0; i < nbAretes; ++i) {
    adj[x[i]].emplace_back(y[i], cost[i]);
    adj[y[i]].emplace_back(x[i], cost[i]);
  }

  vector<bool> reachable(nbSommets);
  reachable[0] = true;
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (u == arrival)
      continue;
    for (auto [v, c] : adj[u])
      if (!reachable[v]) {
        reachable[v] = true;
        q.push(v);
      }
  }

  maxDiv = min(maxDiv, 100);
  vector<double> curDis(nbSommets, INF);
  curDis[0] = 0;
  for (int u = 0; u < nbSommets; ++u)
    if (reachable[u] and effect[u] == 0)
      curDis[u] = 0;

  for (int iter = 0; iter <= maxDiv; ++iter) {
    min_pq<pair<double, int>> pq;
    for (int u = 0; u < nbSommets; ++u)
      if (curDis[u] < INF)
        pq.emplace(curDis[u], u);
    while (!pq.empty()) {
      auto [d, u] = pq.top();
      pq.pop();
      if (d > curDis[u])
        continue;
      for (auto [v, c] : adj[u])
        if (d + c < curDis[v]) {
          curDis[v] = d + c;
          pq.emplace(curDis[v], v);
        }
    }
    if (iter < maxDiv)
      for (int u = 0; u < nbSommets; ++u)
        if (effect[u] == 2 and curDis[u] != INF)
          curDis[u] /= 2;
  }
  return curDis[arrival] == INF ? -1 : curDis[arrival];
}

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 488 KB Correct.
2 Correct 123 ms 476 KB Correct.
3 Correct 122 ms 492 KB Correct.
4 Correct 126 ms 436 KB Correct.
5 Correct 127 ms 468 KB Correct.
6 Correct 171 ms 1844 KB Correct.
7 Correct 228 ms 1828 KB Correct.
8 Correct 99 ms 3404 KB Correct.
9 Correct 77 ms 376 KB Correct.
10 Correct 58 ms 368 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 456 KB Correct.
2 Correct 115 ms 472 KB Correct.
3 Correct 99 ms 476 KB Correct.
4 Correct 65 ms 372 KB Correct.
5 Correct 65 ms 380 KB Correct.
6 Correct 32 ms 1484 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 504 KB Correct.
2 Correct 52 ms 440 KB Correct.
3 Correct 58 ms 492 KB Correct.
4 Correct 92 ms 1456 KB Correct.
5 Correct 45 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 456 KB Correct.
2 Correct 44 ms 484 KB Correct.
3 Correct 35 ms 9204 KB Correct.
4 Correct 58 ms 1432 KB Correct.
5 Correct 47 ms 380 KB Correct.
6 Correct 50 ms 480 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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