Submission #851423

#	Time	Username	Problem	Language	Result	Execution time	Memory
851423		mychecksedad	Cyberland (APIO23_cyberland)	C++17	100 / 100	2663 ms	101424 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 = 2e5;

int _H;
double po[95];
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(!VIS[u] && 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);

  K = min(K, 90);

  po[0] = 1;
  for(int i = 1; i < 95; ++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;
  
  set<array<double, 3>> Q;
  
  Q.insert({0, H, 0});
  
  while(!Q.empty()){
  	auto it = *Q.begin();
    int v = it[1], k = it[2];
    Q.erase(Q.begin());
    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 && k + 1 <= K && (dist[u][k + 1] == -1 || dist[u][k + 1] > dist[v][k] + w / po[k + 1])){
    		Q.erase({dist[u][k + 1], u, k + 1});
      	dist[u][k + 1] = dist[v][k] + w / po[k + 1];
      	Q.insert({dist[u][k + 1], u, k + 1});
    	}
  		if(dist[u][k] == -1 || dist[u][k] > dist[v][k] + w / po[k]){
      	Q.erase({dist[u][k], u, k});
      	dist[u][k] = dist[v][k] + w / po[k];
      	Q.insert({dist[u][k], u, k});
    	}
    }
  }
  if(!vis[0][0]) return -1;
  double ans = -1;
  dfs(0, 0);
  for(int i = 0; i < N; ++i){
    if(VIS[i] && (arr[i] == 0 || i == 0)){
      for(int j = 0; j <= K; ++j){
      	if(dist[i][j] == -1) continue;
        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:45:16: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   45 |   Q.insert({0, H, 0});
      |                ^
cyberland.cpp:58:32: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   58 |       Q.erase({dist[u][k + 1], u, k + 1});
      |                                ^
cyberland.cpp:58:37: warning: narrowing conversion of '(k + 1)' from 'int' to 'double' [-Wnarrowing]
   58 |       Q.erase({dist[u][k + 1], u, k + 1});
      |                                   ~~^~~
cyberland.cpp:60:34: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   60 |        Q.insert({dist[u][k + 1], u, k + 1});
      |                                  ^
cyberland.cpp:60:39: warning: narrowing conversion of '(k + 1)' from 'int' to 'double' [-Wnarrowing]
   60 |        Q.insert({dist[u][k + 1], u, k + 1});
      |                                     ~~^~~
cyberland.cpp:63:29: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   63 |        Q.erase({dist[u][k], u, k});
      |                             ^
cyberland.cpp:63:32: warning: narrowing conversion of 'k' from 'int' to 'double' [-Wnarrowing]
   63 |        Q.erase({dist[u][k], u, k});
      |                                ^
cyberland.cpp:65:30: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   65 |        Q.insert({dist[u][k], u, k});
      |                              ^
cyberland.cpp:65:33: warning: narrowing conversion of 'k' from 'int' to 'double' [-Wnarrowing]
   65 |        Q.insert({dist[u][k], u, k});
      |                                 ^

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