oj.uz

Submission #1112770

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

const int K = 60;
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 46 ms 2908 KB Correct.
2 Correct 46 ms 2896 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 4144 KB Correct.
2 Correct 244 ms 4196 KB Correct.
3 Correct 229 ms 4208 KB Correct.
4 Correct 244 ms 4212 KB Correct.
5 Correct 249 ms 4172 KB Correct.
6 Correct 227 ms 14852 KB Correct.
7 Correct 304 ms 14656 KB Correct.
8 Correct 162 ms 25792 KB Correct.
9 Correct 191 ms 2896 KB Correct.
10 Correct 190 ms 3000 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 4428 KB Correct.
2 Correct 535 ms 4460 KB Correct.
3 Correct 492 ms 4496 KB Correct.
4 Correct 456 ms 2896 KB Correct.
5 Correct 440 ms 2996 KB Correct.
6 Correct 110 ms 13984 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 61256 KB Correct.
2 Correct 853 ms 4676 KB Correct.
3 Correct 688 ms 4888 KB Correct.
4 Correct 748 ms 4872 KB Correct.
5 Correct 538 ms 3840 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 5176 KB Correct.
2 Correct 147 ms 5336 KB Correct.
3 Correct 158 ms 5248 KB Correct.
4 Correct 155 ms 16120 KB Correct.
5 Correct 107 ms 3648 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 5972 KB Correct.
2 Correct 260 ms 5756 KB Correct.
3 Correct 82 ms 83000 KB Correct.
4 Correct 214 ms 16068 KB Correct.
5 Correct 280 ms 3756 KB Correct.
6 Correct 312 ms 5980 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 10204 KB Correct.
2 Correct 108 ms 12108 KB Correct.
3 Correct 1433 ms 104648 KB Correct.
4 Correct 1129 ms 29252 KB Correct.
5 Correct 2986 ms 141128 KB Correct.
6 Correct 1211 ms 69768 KB Correct.
7 Correct 1163 ms 31364 KB Correct.
8 Correct 1131 ms 11176 KB Correct.
9 Correct 632 ms 10140 KB Correct.
10 Correct 610 ms 10452 KB Correct.
11 Correct 1099 ms 9028 KB Correct.
12 Correct 619 ms 10184 KB Correct.
13 Correct 659 ms 10332 KB Correct.
14 Correct 1004 ms 54700 KB Correct.
15 Correct 1295 ms 20452 KB Correct.
16 Correct 618 ms 10152 KB Correct.
17 Correct 738 ms 10164 KB Correct.
18 Correct 711 ms 9288 KB Correct.
19 Correct 1961 ms 11420 KB Correct.
20 Correct 39 ms 7076 KB Correct.
21 Correct 49 ms 7956 KB Correct.
22 Correct 98 ms 14528 KB Correct.

Subtask #8
0.0 / 3.0

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