oj.uz

Submission #892481

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

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

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

int n, h, k;
vector<int> arr;
vector<ld> mn;
vector<vector<vector<ld>>> dis;
vector<vector<pair<int, ld>>> adj;

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 (mn[y] != INF && arr[y] == 2 && divs+1 < min(k+1, 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+1, 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.clear();
    arr = ARR;

    adj.clear();
    adj.resize(n);
    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]));
    }

    mn.clear();
    mn.resize(n);
    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);
        }
    }

    dis.clear();
    dis.resize(2, vector<vector<ld>>(K, vector<ld>(n)));
    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 42 ms 848 KB Correct.
2 Correct 41 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3228 KB Correct.
2 Correct 50 ms 3620 KB Correct.
3 Correct 43 ms 3476 KB Correct.
4 Correct 51 ms 3672 KB Correct.
5 Correct 56 ms 3740 KB Correct.
6 Correct 51 ms 21980 KB Correct.
7 Correct 61 ms 21480 KB Correct.
8 Correct 28 ms 32100 KB Correct.
9 Correct 40 ms 1844 KB Correct.
10 Correct 45 ms 1920 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3416 KB Correct.
2 Correct 61 ms 3480 KB Correct.
3 Correct 49 ms 3404 KB Correct.
4 Correct 50 ms 1812 KB Correct.
5 Correct 52 ms 2300 KB Correct.
6 Correct 13 ms 13148 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3456 KB Correct.
2 Correct 44 ms 3684 KB Correct.
3 Correct 52 ms 3544 KB Correct.
4 Correct 51 ms 21056 KB Correct.
5 Correct 40 ms 1720 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3524 KB Correct.
2 Correct 50 ms 3396 KB Correct.
3 Correct 95 ms 122844 KB Correct.
4 Correct 45 ms 14264 KB Correct.
5 Correct 47 ms 1784 KB Correct.
6 Correct 56 ms 3468 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 848 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -