oj.uz

Submission #751081

# Submission time Handle Problem Language Result Execution time Memory
751081 2023-05-31T04:44:52 Z ND0322 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 67652 KB 
#include <bits/stdc++.h>

using namespace std;




typedef pair<int,int> pii;
typedef tuple<double,int,int> tu;




const double INF = DBL_MAX;

/*

void dfs(int node,vector<int> arr,int K,int H,vector<pii> adj[]){
  visited[node] = true;
  if(!arr[node]){
    adj[0].push_back({node,0});
  }

  if(node == H){
    return;
  }

  for(pii c:adj[node]){
    if(!visited[c.first]){
      dfs(c.first,arr,K,H,adj);
    }
  }
}

*/

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
  vector<pii> adj[N];

  K = min(K,70);

  for(int i = 0; i < M; i++){
    adj[x[i]].push_back({y[i],c[i]});
    adj[y[i]].push_back({x[i],c[i]});
  }

  
  priority_queue<tu,vector<tu>,greater<tu>> pq;

  vector<vector<double>>distances(N,vector<double>(K+1,INF));
  

  //dfs(0,arr,K,H,adj);

  pq.push({0.0,K,0});
  distances[0][K] = 0.0;




  while(!pq.empty()){
    double d= get<0>(pq.top());
    int node = get<2>(pq.top());
    int k = get<1>(pq.top());

    pq.pop();

    if(d != distances[node][k] || node == H) continue;

    


    /*
    if(node == H){
      continue;
    }
    */

    //d != distances[node][k] || 

    for(pii c: adj[node]){
      int child = c.first;
      int weight = c.second;

      if(!arr[child]){
        if(distances[child][k]){
          distances[child][k] = 0;
          pq.push({0,k,child});
          continue;
        }
      }

      

      
      if(arr[child] == 2){
        if(k && distances[child][k-1] > (d + 1.0 * weight)/2.0){
          
          distances[child][k-1] = (d + weight)/2.0;
          pq.push({distances[child][k-1],k-1,child});
        }
      }
     
      if (distances[child][k] > d + 1.0 * weight){
        
        distances[child][k] = d + 1.0 * weight;
        pq.push({distances[child][k],k,child});
      }
      
      
    }
    
  }

  

  

  double ans = INF;

  for(int i = 0; i <=K; i++){
    ans = min(ans,distances[H][i]);
  }

  return (ans >= INF ? -1 : ans);
  
  
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 464 KB Correct.
2 Correct 23 ms 452 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 668 KB Correct.
2 Correct 29 ms 704 KB Correct.
3 Correct 28 ms 688 KB Correct.
4 Correct 31 ms 704 KB Correct.
5 Correct 29 ms 680 KB Correct.
6 Correct 29 ms 3888 KB Correct.
7 Correct 33 ms 3848 KB Correct.
8 Correct 21 ms 7508 KB Correct.
9 Correct 27 ms 340 KB Correct.
10 Correct 30 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 688 KB Correct.
2 Correct 35 ms 636 KB Correct.
3 Correct 28 ms 724 KB Correct.
4 Correct 32 ms 392 KB Correct.
5 Correct 28 ms 392 KB Correct.
6 Correct 6 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 21316 KB Correct.
2 Correct 550 ms 688 KB Correct.
3 Correct 488 ms 788 KB Correct.
4 Correct 512 ms 808 KB Correct.
5 Correct 455 ms 440 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 668 KB Correct.
2 Correct 28 ms 596 KB Correct.
3 Correct 37 ms 648 KB Correct.
4 Correct 28 ms 3648 KB Correct.
5 Correct 25 ms 388 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 664 KB Correct.
2 Correct 26 ms 668 KB Correct.
3 Correct 55 ms 27896 KB Correct.
4 Correct 19 ms 2568 KB Correct.
5 Correct 26 ms 404 KB Correct.
6 Correct 32 ms 712 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 2160 KB Correct.
2 Correct 57 ms 2100 KB Correct.
3 Correct 1605 ms 27336 KB Correct.
4 Correct 1333 ms 7148 KB Correct.
5 Correct 1292 ms 48352 KB Correct.
6 Correct 478 ms 23824 KB Correct.
7 Correct 1256 ms 7184 KB Correct.
8 Correct 1258 ms 1564 KB Correct.
9 Correct 418 ms 1584 KB Correct.
10 Correct 432 ms 2288 KB Correct.
11 Correct 1200 ms 1124 KB Correct.
12 Correct 468 ms 1508 KB Correct.
13 Correct 449 ms 2428 KB Correct.
14 Correct 1063 ms 9204 KB Correct.
15 Correct 1442 ms 3456 KB Correct.
16 Correct 413 ms 1540 KB Correct.
17 Correct 535 ms 1508 KB Correct.
18 Correct 538 ms 1520 KB Correct.
19 Correct 1586 ms 2208 KB Correct.
20 Correct 30 ms 464 KB Correct.
21 Correct 35 ms 1172 KB Correct.
22 Correct 36 ms 3176 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1990 ms 7264 KB Correct.
2 Correct 210 ms 4804 KB Correct.
3 Correct 723 ms 67652 KB Correct.
4 Execution timed out 3055 ms 4580 KB Time limit exceeded
5 Halted 0 ms 0 KB -