Submission #851384

#	Time	Username	Problem	Language	Result	Execution time	Memory
851384		mychecksedad	Cyberland (APIO23_cyberland)	C++17	0 / 100	1339 ms	2097152 KiB

cyberland

// #include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define all(x) x.begin(), x.end()
const int SZ = 1e6;

int _H;
double po[35];
vector<pair<int, double>> g[SZ];
vector<bool> VIS;
void dfs(int v, int p){
  VIS[v] = 1;
  for(auto U: g[v]){
    int u = U.first;
    if(u != p && u != _H)
      dfs(u, v);
  }
}

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) {
  for(int i = 0; i < N; ++i) g[i].clear();
  _H = H;
  VIS.clear();
  VIS.resize(N);

  po[0] = 1;
  for(int i = 1; i < 35; ++i) po[i] = po[i - 1] * 2;
  
  vector<vector<double>> dist(N);
  vector<vector<bool>> vis(N);
  for(int i = 0; i < M; ++i)
    g[x[i]].pb({y[i], c[i]}),
    g[y[i]].pb({x[i], c[i]});

  for(int i = 0; i < N; ++i) dist[i].resize(K + 1, -1), vis[i].resize(K + 1);
  
  dist[H][0] = 0;
  
  priority_queue<array<double, 3>> Q;
  
  Q.push({0, H, 0});
  
  while(!Q.empty()){
    int v = Q.top()[1], k = Q.top()[2];
    Q.pop();
    if(vis[v][k]) continue;
    vis[v][k] = 1;
    for(auto U: g[v]){
      int u = U.first;
      if(u == H) continue;
      double w = U.second;
    	if(arr[v] == 2 && (dist[u][k + 1] == -1 || dist[u][k + 1] > dist[v][k] + w / po[k + 1])){
      	dist[u][k + 1] = dist[v][k] + w / po[k + 1];
      	Q.push({-dist[u][k + 1], u, k + 1});
    	}
  		if(dist[u][k] == -1 || dist[u][k] > dist[v][k] + w / po[k]){
      	dist[u][k] = dist[v][k] + w / po[k];
      	Q.push({-dist[u][k], u, k});
    	}
    }
  }
  if(!vis[0][0]) return -1;
  double ans = *min_element(all(dist[0]));
  dfs(0, 0);
  for(int i = 0; i < N; ++i){
    if(VIS[i] && arr[i] == 0){
      for(int j = 0; j <= K; ++j){
        ans = ans == -1 || ans > dist[i][j] ? dist[i][j] : ans;
      }
    }
  }

  return ans;
}

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:43:14: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   43 |   Q.push({0, H, 0});
      |              ^
cyberland.cpp:56:33: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   56 |        Q.push({-dist[u][k + 1], u, k + 1});
      |                                 ^
cyberland.cpp:56:38: warning: narrowing conversion of '(k + 1)' from 'int' to 'double' [-Wnarrowing]
   56 |        Q.push({-dist[u][k + 1], u, k + 1});
      |                                    ~~^~~
cyberland.cpp:60:29: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   60 |        Q.push({-dist[u][k], u, k});
      |                             ^
cyberland.cpp:60:32: warning: narrowing conversion of 'k' from 'int' to 'double' [-Wnarrowing]
   60 |        Q.push({-dist[u][k], u, k});
      |                                ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3