oj.uz

Submission #1112769

# Submission time Handle Problem Language Result Execution time Memory
1112769 2024-11-14T19:38:30 Z PagodePaiva Cyberland (APIO23_cyberland) C++17
97 / 100
 2863 ms 123240 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) {
    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 51 ms 2896 KB Correct.
2 Correct 44 ms 2876 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 3740 KB Correct.
2 Correct 238 ms 3720 KB Correct.
3 Correct 235 ms 3744 KB Correct.
4 Correct 239 ms 3744 KB Correct.
5 Correct 237 ms 3716 KB Correct.
6 Correct 242 ms 10604 KB Correct.
7 Correct 295 ms 10308 KB Correct.
8 Correct 142 ms 16832 KB Correct.
9 Correct 191 ms 2896 KB Correct.
10 Correct 186 ms 2896 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 3972 KB Correct.
2 Correct 506 ms 4548 KB Correct.
3 Correct 481 ms 4484 KB Correct.
4 Correct 433 ms 2976 KB Correct.
5 Correct 434 ms 2896 KB Correct.
6 Correct 117 ms 10432 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 34756 KB Correct.
2 Correct 771 ms 3280 KB Correct.
3 Correct 645 ms 3828 KB Correct.
4 Correct 727 ms 3852 KB Correct.
5 Correct 520 ms 3068 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 3848 KB Correct.
2 Correct 136 ms 3840 KB Correct.
3 Correct 145 ms 3836 KB Correct.
4 Correct 150 ms 10796 KB Correct.
5 Correct 99 ms 2968 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 4452 KB Correct.
2 Correct 249 ms 4792 KB Correct.
3 Correct 55 ms 44740 KB Correct.
4 Correct 232 ms 12484 KB Correct.
5 Correct 264 ms 3276 KB Correct.
6 Correct 299 ms 5088 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 6036 KB Correct.
2 Correct 108 ms 8272 KB Correct.
3 Correct 1499 ms 57284 KB Correct.
4 Correct 1172 ms 16544 KB Correct.
5 Correct 2863 ms 123240 KB Correct.
6 Correct 1118 ms 60880 KB Correct.
7 Correct 1166 ms 16436 KB Correct.
8 Correct 1191 ms 5060 KB Correct.
9 Correct 620 ms 5776 KB Correct.
10 Correct 593 ms 6164 KB Correct.
11 Correct 1103 ms 3880 KB Correct.
12 Correct 643 ms 5816 KB Correct.
13 Correct 654 ms 6760 KB Correct.
14 Correct 1014 ms 29400 KB Correct.
15 Correct 1281 ms 10288 KB Correct.
16 Correct 641 ms 5668 KB Correct.
17 Correct 742 ms 5880 KB Correct.
18 Correct 723 ms 5388 KB Correct.
19 Correct 1910 ms 5860 KB Correct.
20 Correct 39 ms 3236 KB Correct.
21 Correct 49 ms 4408 KB Correct.
22 Correct 103 ms 9860 KB Correct.

Subtask #8
0.0 / 3.0

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