oj.uz

Submission #773858

# Submission time Handle Problem Language Result Execution time Memory
773858 2023-07-05T09:10:36 Z peijar Cyberland (APIO23_cyberland) C++17
100 / 100
 2474 ms 17496 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]);
  }
  dbg(maxDiv, arrival);
  dbg(x);
  dbg(y);
  dbg(cost);
  dbg(effect);

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 588 KB Correct.
2 Correct 51 ms 724 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 836 KB Correct.
2 Correct 312 ms 1428 KB Correct.
3 Correct 296 ms 1424 KB Correct.
4 Correct 309 ms 1336 KB Correct.
5 Correct 327 ms 1460 KB Correct.
6 Correct 340 ms 2680 KB Correct.
7 Correct 455 ms 2536 KB Correct.
8 Correct 201 ms 3772 KB Correct.
9 Correct 108 ms 1052 KB Correct.
10 Correct 104 ms 1116 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 1500 KB Correct.
2 Correct 329 ms 1228 KB Correct.
3 Correct 308 ms 1416 KB Correct.
4 Correct 121 ms 800 KB Correct.
5 Correct 123 ms 1112 KB Correct.
6 Correct 79 ms 1816 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 9040 KB Correct.
2 Correct 181 ms 1292 KB Correct.
3 Correct 158 ms 1468 KB Correct.
4 Correct 167 ms 1412 KB Correct.
5 Correct 84 ms 1124 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 1324 KB Correct.
2 Correct 137 ms 1280 KB Correct.
3 Correct 154 ms 1324 KB Correct.
4 Correct 195 ms 2196 KB Correct.
5 Correct 59 ms 1072 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 1256 KB Correct.
2 Correct 133 ms 1252 KB Correct.
3 Correct 39 ms 11148 KB Correct.
4 Correct 129 ms 2108 KB Correct.
5 Correct 76 ms 1212 KB Correct.
6 Correct 160 ms 1080 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 1364 KB Correct.
2 Correct 27 ms 648 KB Correct.
3 Correct 749 ms 16912 KB Correct.
4 Correct 517 ms 5764 KB Correct.
5 Correct 596 ms 11528 KB Correct.
6 Correct 257 ms 8740 KB Correct.
7 Correct 516 ms 4996 KB Correct.
8 Correct 403 ms 2584 KB Correct.
9 Correct 156 ms 1404 KB Correct.
10 Correct 165 ms 1348 KB Correct.
11 Correct 346 ms 2440 KB Correct.
12 Correct 179 ms 1288 KB Correct.
13 Correct 168 ms 1332 KB Correct.
14 Correct 411 ms 8932 KB Correct.
15 Correct 430 ms 4044 KB Correct.
16 Correct 165 ms 1280 KB Correct.
17 Correct 200 ms 1468 KB Correct.
18 Correct 198 ms 1472 KB Correct.
19 Correct 569 ms 2360 KB Correct.
20 Correct 8 ms 340 KB Correct.
21 Correct 13 ms 468 KB Correct.
22 Correct 18 ms 1108 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 1160 KB Correct.
2 Correct 78 ms 724 KB Correct.
3 Correct 2207 ms 17496 KB Correct.
4 Correct 651 ms 3424 KB Correct.
5 Correct 1854 ms 11652 KB Correct.
6 Correct 752 ms 8460 KB Correct.
7 Correct 1062 ms 7612 KB Correct.
8 Correct 613 ms 2108 KB Correct.
9 Correct 418 ms 1400 KB Correct.
10 Correct 428 ms 1428 KB Correct.
11 Correct 269 ms 1484 KB Correct.
12 Correct 492 ms 1480 KB Correct.
13 Correct 462 ms 1456 KB Correct.
14 Correct 2126 ms 9152 KB Correct.
15 Correct 2474 ms 8896 KB Correct.
16 Correct 896 ms 4052 KB Correct.
17 Correct 690 ms 1672 KB Correct.
18 Correct 450 ms 1096 KB Correct.
19 Correct 556 ms 844 KB Correct.
20 Correct 528 ms 812 KB Correct.
21 Correct 1736 ms 476 KB Correct.
22 Correct 17 ms 424 KB Correct.
23 Correct 33 ms 384 KB Correct.
24 Correct 51 ms 1108 KB Correct.