oj.uz

답안 #773810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
773810 2023-07-05T08:49:22 Z peijar 사이버랜드 (APIO23_cyberland) C++17
44 / 100
 815 ms 9800 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 (d > nxtDis[u])
        continue;
      for (auto [v, c] : adj[u])
        if (d + c < nxtDis[v]) {
          nxtDis[v] = d + c;
          pq.emplace(curDis[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)
        curDis[u] = min(curDis[u], nxtDis[u] / 2);
    }
  }
  return curDis[arrival] == INF ? -1 : curDis[arrival];
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 372 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 448 KB Correct.
2 Correct 285 ms 500 KB Correct.
3 Correct 277 ms 468 KB Correct.
4 Correct 275 ms 492 KB Correct.
5 Correct 272 ms 472 KB Correct.
6 Correct 275 ms 1888 KB Correct.
7 Correct 357 ms 1840 KB Correct.
8 Correct 149 ms 3412 KB Correct.
9 Correct 124 ms 392 KB Correct.
10 Correct 118 ms 396 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 369 ms 552 KB Correct.
2 Correct 350 ms 500 KB Correct.
3 Correct 326 ms 548 KB Correct.
4 Correct 151 ms 400 KB Correct.
5 Correct 154 ms 340 KB Correct.
6 Correct 80 ms 1672 KB Correct.

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 567 ms 8632 KB Correct.
2 Incorrect 327 ms 1272 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 440 KB Correct.
2 Correct 124 ms 480 KB Correct.
3 Correct 155 ms 472 KB Correct.
4 Correct 143 ms 1484 KB Correct.
5 Correct 65 ms 380 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 492 KB Correct.
2 Correct 145 ms 452 KB Correct.
3 Correct 38 ms 9800 KB Correct.
4 Correct 139 ms 1456 KB Correct.
5 Correct 88 ms 384 KB Correct.
6 Correct 181 ms 488 KB Correct.

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 262 ms 428 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 815 ms 492 KB Wrong Answer.
2 Halted 0 ms 0 KB -