oj.uz

Submission #1112773

# Submission time Handle Problem Language Result Execution time Memory
1112773 2024-11-14T19:40:41 Z PagodePaiva Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 190808 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
//#define int long long
#define dp dist
using namespace std;

const int K = 120;
const int N = 100010;

vector <pair <int, int>> g[N];
double dist[N][K][2];
int op[N];

double solve(int32_t n, int32_t m, int32_t k, int32_t h, std::vector<int32_t> x, std::vector<int32_t> y, std::vector<int32_t> c, std::vector<int32_t> arr) {
    k = min(k, K);
    for(int i = 0;i < n;i++){
      g[i].clear();
    }
    for(int i = 0;i < m;i++){
      int a = x[i], b = y[i], w = c[i];
      g[a].push_back({b, w});
      g[b].push_back({a, w});
    }
    for(int i = 0;i < n;i++){
      op[i] = arr[i];
    }
    for(int i = 0;i < n;i++){
      for(int j = 0;j <= k;j++){
        dist[i][j][0] = dist[i][j][1] = 1e18;
      }
    }
    priority_queue <pair <double, array <int, 3>>> pq;
    for(int i = 0;i <= k;i++){
      dist[0][i][0] = 0;
      pq.push({0, {0, i, 0}});
    }
    while(!pq.empty()){
      auto [d,cu] = pq.top();
      auto [v, i, flag] = cu;
      pq.pop();
      d *= -1;
      if(d != dist[v][i][flag]) continue;
      if(v == h) continue;
      if(flag == 0){
        if(op[v] == 0){
          if(dist[v][i][1] > 0){
            dist[v][i][1] = 0;
            pq.push({-dist[v][i][1], {v, i, 1}});
          }
        }
        else if(op[v] == 2){
          if(i > 0){
            if(dist[v][i-1][1] > (dist[v][i][0])/(2.0)){
              dist[v][i-1][1] = (dist[v][i][0])/(2.0);
              pq.push({-dist[v][i-1][1], {v, i-1, 1}});
            }
          }
        }
      }
      for(auto [x, w] : g[v]){
        if(dist[v][i][flag]+w < dist[x][i][0]){
          dist[x][i][0] = dist[v][i][flag]+w;
          pq.push({-dist[x][i][0], {x, i, 0}});
        }
      }
    }
  double res = 1e18;
  for(int i = 0;i <= k;i++){
    res = min(res, dp[h][i][0]);
  }        
  return (res == 1e18 ? -1 : res);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6312 KB Correct.
2 Correct 55 ms 6576 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 8720 KB Correct.
2 Correct 249 ms 8648 KB Correct.
3 Correct 243 ms 8720 KB Correct.
4 Correct 253 ms 8712 KB Correct.
5 Correct 250 ms 8700 KB Correct.
6 Correct 232 ms 27504 KB Correct.
7 Correct 296 ms 25620 KB Correct.
8 Correct 136 ms 45652 KB Correct.
9 Correct 190 ms 6304 KB Correct.
10 Correct 184 ms 6392 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 8960 KB Correct.
2 Correct 511 ms 9940 KB Correct.
3 Correct 494 ms 10000 KB Correct.
4 Correct 444 ms 7240 KB Correct.
5 Correct 436 ms 7240 KB Correct.
6 Correct 104 ms 25020 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 117660 KB Correct.
2 Correct 788 ms 8344 KB Correct.
3 Correct 655 ms 8264 KB Correct.
4 Correct 711 ms 8352 KB Correct.
5 Correct 529 ms 6352 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 8760 KB Correct.
2 Correct 134 ms 8792 KB Correct.
3 Correct 146 ms 8752 KB Correct.
4 Correct 154 ms 26032 KB Correct.
5 Correct 101 ms 6312 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 9204 KB Correct.
2 Correct 255 ms 7376 KB Correct.
3 Correct 108 ms 151560 KB Correct.
4 Correct 208 ms 24664 KB Correct.
5 Correct 258 ms 6400 KB Correct.
6 Correct 300 ms 9456 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 11012 KB Correct.
2 Correct 110 ms 13364 KB Correct.
3 Correct 1621 ms 190808 KB Correct.
4 Correct 1226 ms 47260 KB Correct.
5 Correct 2857 ms 174408 KB Correct.
6 Correct 1116 ms 77984 KB Correct.
7 Correct 1185 ms 51256 KB Correct.
8 Correct 1137 ms 12948 KB Correct.
9 Correct 617 ms 10648 KB Correct.
10 Correct 609 ms 11092 KB Correct.
11 Correct 1114 ms 8836 KB Correct.
12 Correct 635 ms 10952 KB Correct.
13 Correct 658 ms 10912 KB Correct.
14 Correct 1075 ms 95256 KB Correct.
15 Correct 1322 ms 30244 KB Correct.
16 Correct 606 ms 10596 KB Correct.
17 Correct 756 ms 10764 KB Correct.
18 Correct 753 ms 9764 KB Correct.
19 Correct 1934 ms 10912 KB Correct.
20 Correct 39 ms 6564 KB Correct.
21 Correct 50 ms 7384 KB Correct.
22 Correct 103 ms 13760 KB Correct.

Subtask #8
0.0 / 3.0

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