oj.uz

Submission #760981

# Submission time Handle Problem Language Result Execution time Memory
760981 2023-06-19T01:42:50 Z ND0322 Cyberland (APIO23_cyberland) C++17
100 / 100
 146 ms 67928 KB 
#include <bits/stdc++.h>


using namespace std;




typedef pair<int,int> pii;
typedef tuple<double,int,int> tu;
int parents[100005];




const double INF = DBL_MAX;

int find(int x){
  int i = x; 
  while(i != parents[i]){
    parents[i] = parents[parents[i]];
    i = parents[i];
  }
  return i;
}

void Union(int x,int y){
  parents[find(x)] = find(y);
}



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 < N; i++){
  parents[i] = i;
}

  for(int i = 0; i < M; i++){
    if(x[i] != H && y[i] != H){
      if(find(x[i]) != find(y[i]))Union(x[i],y[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);

  vector<double> twos(K + 1, 1);
  for(int i = 1; i <= K; i++){
    twos[i] = twos[i-1]/2;
  }

  arr[0] = 0;
  pq.push({0.0,K,H});
  distances[H][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(node == H){
      continue;
    }
    */

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

    if (distances[node][k] < d)
			continue;

    if(!arr[node]){
      return d;
    }

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

      if(find(child) != find(0)){
        continue;
      }

      

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

  return -1;

  

  

  
  
  
}

/*

int main() {

  
  //Final solution: we divide by 2 whenever we can and we start from the end node. Dsu to see if child nodes can reach node 0, and stop when seeing a node with arr[v] == 0 because reverse
  

 
}
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Correct.
2 Correct 17 ms 424 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 676 KB Correct.
2 Correct 21 ms 712 KB Correct.
3 Correct 20 ms 704 KB Correct.
4 Correct 21 ms 596 KB Correct.
5 Correct 20 ms 692 KB Correct.
6 Correct 17 ms 3860 KB Correct.
7 Correct 22 ms 3788 KB Correct.
8 Correct 10 ms 7508 KB Correct.
9 Correct 20 ms 404 KB Correct.
10 Correct 20 ms 396 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 596 KB Correct.
2 Correct 20 ms 668 KB Correct.
3 Correct 19 ms 724 KB Correct.
4 Correct 20 ms 412 KB Correct.
5 Correct 20 ms 400 KB Correct.
6 Correct 4 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 21460 KB Correct.
2 Correct 19 ms 712 KB Correct.
3 Correct 19 ms 740 KB Correct.
4 Correct 18 ms 744 KB Correct.
5 Correct 21 ms 340 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 708 KB Correct.
2 Correct 23 ms 596 KB Correct.
3 Correct 22 ms 688 KB Correct.
4 Correct 26 ms 3668 KB Correct.
5 Correct 21 ms 412 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 696 KB Correct.
2 Correct 19 ms 676 KB Correct.
3 Correct 46 ms 28152 KB Correct.
4 Correct 14 ms 2492 KB Correct.
5 Correct 20 ms 340 KB Correct.
6 Correct 21 ms 680 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 656 KB Correct.
2 Correct 3 ms 852 KB Correct.
3 Correct 51 ms 26472 KB Correct.
4 Correct 40 ms 6864 KB Correct.
5 Correct 39 ms 15592 KB Correct.
6 Correct 24 ms 7244 KB Correct.
7 Correct 40 ms 6828 KB Correct.
8 Correct 41 ms 1444 KB Correct.
9 Correct 20 ms 700 KB Correct.
10 Correct 20 ms 668 KB Correct.
11 Correct 42 ms 732 KB Correct.
12 Correct 21 ms 712 KB Correct.
13 Correct 23 ms 708 KB Correct.
14 Correct 41 ms 8720 KB Correct.
15 Correct 51 ms 2588 KB Correct.
16 Correct 21 ms 696 KB Correct.
17 Correct 23 ms 676 KB Correct.
18 Correct 22 ms 684 KB Correct.
19 Correct 40 ms 628 KB Correct.
20 Correct 2 ms 340 KB Correct.
21 Correct 2 ms 620 KB Correct.
22 Correct 3 ms 980 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1000 KB Correct.
2 Correct 4 ms 1364 KB Correct.
3 Correct 94 ms 67928 KB Correct.
4 Correct 39 ms 3000 KB Correct.
5 Correct 40 ms 26684 KB Correct.
6 Correct 25 ms 10444 KB Correct.
7 Correct 41 ms 12868 KB Correct.
8 Correct 43 ms 1344 KB Correct.
9 Correct 22 ms 1020 KB Correct.
10 Correct 23 ms 1044 KB Correct.
11 Correct 146 ms 532 KB Correct.
12 Correct 22 ms 992 KB Correct.
13 Correct 23 ms 1116 KB Correct.
14 Correct 52 ms 27420 KB Correct.
15 Correct 55 ms 33848 KB Correct.
16 Correct 42 ms 11680 KB Correct.
17 Correct 44 ms 2720 KB Correct.
18 Correct 22 ms 1028 KB Correct.
19 Correct 27 ms 1004 KB Correct.
20 Correct 25 ms 1000 KB Correct.
21 Correct 44 ms 980 KB Correct.
22 Correct 3 ms 340 KB Correct.
23 Correct 2 ms 868 KB Correct.
24 Correct 4 ms 1180 KB Correct.