oj.uz

Submission #892474

# Submission time Handle Problem Language Result Execution time Memory
892474 2023-12-25T11:43:56 Z d4xn Cyberland (APIO23_cyberland) C++17
49 / 100
 3000 ms 329552 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define tp3 tuple<ld, int, int>

const int N = 1e5+5, K = 51;
const ld D = 2, INF = LLONG_MAX;

int n, h, k;
ld mn[N], dis[2][K][N];
vector<int> arr;
vector<pair<int, ld>> adj[N];

void dijkstra(int x, int idx) {
    priority_queue<tp3> pq;
    if (idx == 1) {
      for (int i = 0; i < n; i++) {
        if (arr[i] || dis[0][0][i] == INF) continue;
        pq.push(make_tuple(-0, 0, i));
      }
    }
    else {
      pq.push(make_tuple(-0, 0, x));
    }

    while (!pq.empty()) {
      ld d = -get<0>(pq.top());
      int divs = get<1>(pq.top());
      int y = get<2>(pq.top());
      pq.pop();

      if (dis[idx][divs][y] <= d) continue;
      dis[idx][divs][y] = d;

      if (y == h) continue;

      if (arr[y] == 2 && divs+1 < min(k, K) && dis[idx][divs+1][y] > ((d+mn[y]) / D)) {
        pq.push(make_tuple(-((d+mn[y]) / D), divs+1, y));
      }

      for (auto& [z, d2] : adj[y]) {
        if (dis[idx][divs][z] > (d+d2)) {
          pq.push(make_tuple(-(d+d2), divs, z));
        }

        if (arr[z] == 2 && divs+1 < min(k, K) && dis[idx][divs+1][z] > ((d+d2) / D)) {
          pq.push(make_tuple(-((d+d2) / D), divs+1, z));
        }
      }
    }
}

double solve(int N, int m, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> ARR) {
    n = N;
    h = H;
    k = K;
    arr = ARR;

    for (int i = 0; i < n; i++) {
      adj[i].clear();
    }
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(make_pair(y[i], c[i]));
        adj[y[i]].push_back(make_pair(x[i], c[i]));
    }
    for (int i = 0; i < n; i++) {
        mn[i] = INF;
        for (auto& [j, d] : adj[i]) {
          if (j == h) continue;
          
          mn[i] = min(mn[i], d);
        }
    }

    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < K; j++) {
        for (int k = 0; k < n; k++) {
          dis[i][j][k] = INF;
        }
      }
    }
    dijkstra(0, 0);
    dijkstra(0, 1);

    ld ans = INF;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < min(K, k+1); j++) {
        ans = min(ans, dis[i][j][h]);
      }
    }

    return (ans == INF ? (ld)(-1) : ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 101536 KB Correct.
2 Correct 36 ms 101464 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 101836 KB Correct.
2 Correct 47 ms 102304 KB Correct.
3 Correct 38 ms 101976 KB Correct.
4 Correct 39 ms 102096 KB Correct.
5 Correct 38 ms 102160 KB Correct.
6 Correct 36 ms 103204 KB Correct.
7 Correct 45 ms 103512 KB Correct.
8 Correct 26 ms 104020 KB Correct.
9 Correct 36 ms 101720 KB Correct.
10 Correct 36 ms 101724 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 101980 KB Correct.
2 Correct 49 ms 101968 KB Correct.
3 Correct 50 ms 102136 KB Correct.
4 Correct 54 ms 101716 KB Correct.
5 Correct 47 ms 101724 KB Correct.
6 Correct 20 ms 102616 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 109396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 102268 KB Correct.
2 Correct 41 ms 102464 KB Correct.
3 Correct 40 ms 102324 KB Correct.
4 Correct 44 ms 104736 KB Correct.
5 Correct 39 ms 101576 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 102284 KB Correct.
2 Correct 41 ms 102232 KB Correct.
3 Correct 72 ms 113236 KB Correct.
4 Correct 36 ms 103736 KB Correct.
5 Correct 43 ms 101884 KB Correct.
6 Correct 45 ms 102244 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3030 ms 129596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 329552 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -