oj.uz

Submission #756726

# Submission time Handle Problem Language Result Execution time Memory
756726 2023-06-12T06:45:41 Z vioalbert Cyberland (APIO23_cyberland) C++17
100 / 100
 1366 ms 13352 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...)
#endif

const double INF = 1e15;

double solve(int N, int M, int K, int H, vector<int> x,
             vector<int> y, vector<int> c, vector<int> arr) {
  vector adj(N, vector<pair<int, int>>());
  for(int i = 0; i < M; i++) {
    if(x[i] != H) adj[x[i]].emplace_back(y[i], c[i]);
    if(y[i] != H) adj[y[i]].emplace_back(x[i], c[i]);
  }
  vector<int> mark(N, 0);
  const auto connected = [&](const auto &self, int u, int target) -> bool {
    if(u == target) return true;
    mark[u] = 1;
    for(auto [v, c] : adj[u]) if(!mark[v]) {
      if(self(self, v, target)) return true;
    }
    return false;
  };
  if(!connected(connected, 0, H)) {
    return -1.0;
  }
  const auto dijkstra = [&](const vector<int> &sources, vector<int> &vis,
                            vector<double> &dist) {
    using state = pair<double, int>; // dist, node
    fill(vis.begin(), vis.end(), 0);
    priority_queue<state, vector<state>, greater<state>> pq;
    for(int i : sources) pq.push({dist[i], i});
    while(!pq.empty()) {
      int u = pq.top().second; pq.pop();
      if(vis[u]) continue;
      vis[u] = 1;
      for(auto [v, c] : adj[u]) {
        if(dist[v] > dist[u] + c) {
          pq.push({dist[v] = dist[u] + c, v});
        }
      }
    }
  };
  vector<int> vis(N, 0);
  vector<int> sources{0};
  vector<double> dist(N, INF);
  for(int i : sources)
    dist[i] = 0.0;
  dijkstra(sources, vis, dist);
  for(int i = 1; i < N; i++) if(vis[i] && arr[i] == 0)
    sources.push_back(i);
  fill(dist.begin(), dist.end(), INF);
  for(int i : sources)
    dist[i] = 0.0;
  vector<double> new_dist(N);
  double ans = INF;
  for(int it = 0; it <= min(K, 95); it++) {
    if(it == 1) {
      sources.clear();
      for(int i = 0; i < N; i++) if(arr[i] != 1 && vis[i])
        sources.push_back(i);
      fill(mark.begin(), mark.end(), 0);
      bool ok = 0;
      for(int i : sources)
        ok |= connected(connected, i, H);
      if(!ok) break;
    }
    if(it > 0) {
      for(int i = 0; i < N; i++) {
        if(arr[i] == 0) new_dist[i] = 0.0;
        else if(arr[i] == 1) new_dist[i] = INF;
        else {
          new_dist[i] = INF;
          for(auto [v, c] : adj[i]) if(v != H)
            new_dist[i] = min(new_dist[i], (dist[v] + c) / 2.0);
        }
      }
      swap(dist, new_dist);
    }
    dijkstra(sources, vis, dist);
    ans = min(ans, dist[H]);
  }
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 468 KB Correct.
2 Correct 24 ms 400 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 440 KB Correct.
2 Correct 32 ms 444 KB Correct.
3 Correct 32 ms 468 KB Correct.
4 Correct 32 ms 468 KB Correct.
5 Correct 31 ms 468 KB Correct.
6 Correct 27 ms 1400 KB Correct.
7 Correct 39 ms 1456 KB Correct.
8 Correct 16 ms 2644 KB Correct.
9 Correct 28 ms 404 KB Correct.
10 Correct 31 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 432 KB Correct.
2 Correct 153 ms 436 KB Correct.
3 Correct 138 ms 472 KB Correct.
4 Correct 121 ms 388 KB Correct.
5 Correct 120 ms 368 KB Correct.
6 Correct 42 ms 1464 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 7444 KB Correct.
2 Correct 98 ms 460 KB Correct.
3 Correct 87 ms 516 KB Correct.
4 Correct 96 ms 436 KB Correct.
5 Correct 66 ms 396 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 488 KB Correct.
2 Correct 28 ms 416 KB Correct.
3 Correct 31 ms 468 KB Correct.
4 Correct 32 ms 1308 KB Correct.
5 Correct 25 ms 384 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 432 KB Correct.
2 Correct 64 ms 460 KB Correct.
3 Correct 43 ms 7412 KB Correct.
4 Correct 70 ms 1244 KB Correct.
5 Correct 62 ms 368 KB Correct.
6 Correct 77 ms 464 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 432 KB Correct.
2 Correct 16 ms 468 KB Correct.
3 Correct 524 ms 11764 KB Correct.
4 Correct 270 ms 2728 KB Correct.
5 Correct 348 ms 7920 KB Correct.
6 Correct 140 ms 5324 KB Correct.
7 Correct 272 ms 3020 KB Correct.
8 Correct 222 ms 764 KB Correct.
9 Correct 102 ms 524 KB Correct.
10 Correct 75 ms 476 KB Correct.
11 Correct 199 ms 716 KB Correct.
12 Correct 89 ms 428 KB Correct.
13 Correct 89 ms 464 KB Correct.
14 Correct 266 ms 6120 KB Correct.
15 Correct 255 ms 1764 KB Correct.
16 Correct 76 ms 424 KB Correct.
17 Correct 99 ms 448 KB Correct.
18 Correct 83 ms 464 KB Correct.
19 Correct 233 ms 340 KB Correct.
20 Correct 6 ms 316 KB Correct.
21 Correct 6 ms 340 KB Correct.
22 Correct 10 ms 852 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 432 KB Correct.
2 Correct 34 ms 468 KB Correct.
3 Correct 303 ms 13352 KB Correct.
4 Correct 313 ms 1072 KB Correct.
5 Correct 931 ms 8044 KB Correct.
6 Correct 335 ms 5400 KB Correct.
7 Correct 598 ms 4808 KB Correct.
8 Correct 301 ms 672 KB Correct.
9 Correct 180 ms 540 KB Correct.
10 Correct 152 ms 432 KB Correct.
11 Correct 203 ms 564 KB Correct.
12 Correct 189 ms 460 KB Correct.
13 Correct 178 ms 416 KB Correct.
14 Correct 1366 ms 6920 KB Correct.
15 Correct 1242 ms 6168 KB Correct.
16 Correct 424 ms 2304 KB Correct.
17 Correct 324 ms 760 KB Correct.
18 Correct 169 ms 412 KB Correct.
19 Correct 219 ms 448 KB Correct.
20 Correct 183 ms 440 KB Correct.
21 Correct 574 ms 340 KB Correct.
22 Correct 12 ms 340 KB Correct.
23 Correct 13 ms 392 KB Correct.
24 Correct 22 ms 852 KB Correct.