oj.uz

Submission #1112767

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

const int K = 31;
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) {
    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 45 ms 2840 KB Correct.
2 Correct 46 ms 2888 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 3788 KB Correct.
2 Correct 252 ms 3716 KB Correct.
3 Correct 232 ms 3736 KB Correct.
4 Correct 236 ms 3720 KB Correct.
5 Correct 244 ms 3760 KB Correct.
6 Correct 253 ms 10348 KB Correct.
7 Correct 315 ms 10296 KB Correct.
8 Correct 151 ms 16836 KB Correct.
9 Correct 188 ms 3064 KB Correct.
10 Correct 185 ms 2896 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 3988 KB Correct.
2 Correct 511 ms 4676 KB Correct.
3 Correct 466 ms 4060 KB Correct.
4 Correct 429 ms 3004 KB Correct.
5 Correct 438 ms 2896 KB Correct.
6 Correct 105 ms 10472 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 34972 KB Correct.
2 Correct 784 ms 3400 KB Correct.
3 Correct 688 ms 3336 KB Correct.
4 Correct 720 ms 3424 KB Correct.
5 Correct 524 ms 2984 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3796 KB Correct.
2 Correct 145 ms 3776 KB Correct.
3 Correct 150 ms 3800 KB Correct.
4 Correct 161 ms 10792 KB Correct.
5 Correct 104 ms 2896 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 4456 KB Correct.
2 Correct 260 ms 4552 KB Correct.
3 Correct 58 ms 46152 KB Correct.
4 Correct 229 ms 13008 KB Correct.
5 Correct 257 ms 3036 KB Correct.
6 Correct 302 ms 4592 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 6080 KB Correct.
2 Correct 106 ms 8332 KB Correct.
3 Correct 1501 ms 57240 KB Correct.
4 Correct 1149 ms 15284 KB Correct.
5 Correct 2787 ms 123196 KB Correct.
6 Correct 1237 ms 62588 KB Correct.
7 Correct 1223 ms 18460 KB Correct.
8 Correct 1148 ms 6992 KB Correct.
9 Correct 626 ms 6796 KB Correct.
10 Correct 597 ms 6820 KB Correct.
11 Correct 1121 ms 5528 KB Correct.
12 Correct 608 ms 6856 KB Correct.
13 Correct 665 ms 6896 KB Correct.
14 Correct 998 ms 31628 KB Correct.
15 Correct 1297 ms 12360 KB Correct.
16 Correct 611 ms 6584 KB Correct.
17 Correct 731 ms 6692 KB Correct.
18 Correct 720 ms 6228 KB Correct.
19 Correct 1915 ms 7832 KB Correct.
20 Correct 40 ms 3236 KB Correct.
21 Correct 49 ms 4552 KB Correct.
22 Correct 110 ms 9920 KB Correct.

Subtask #8
0.0 / 3.0

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