oj.uz

Submission #851423

# Submission time Handle Problem Language Result Execution time Memory
851423 2023-09-19T18:04:38 Z mychecksedad Cyberland (APIO23_cyberland) C++17
100 / 100
 2663 ms 101424 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5464 KB Correct.
2 Correct 20 ms 5536 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6232 KB Correct.
2 Correct 35 ms 6744 KB Correct.
3 Correct 30 ms 6480 KB Correct.
4 Correct 31 ms 6480 KB Correct.
5 Correct 32 ms 6488 KB Correct.
6 Correct 28 ms 10256 KB Correct.
7 Correct 38 ms 10540 KB Correct.
8 Correct 20 ms 13912 KB Correct.
9 Correct 38 ms 6112 KB Correct.
10 Correct 29 ms 5976 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6224 KB Correct.
2 Correct 31 ms 6488 KB Correct.
3 Correct 29 ms 6480 KB Correct.
4 Correct 31 ms 5968 KB Correct.
5 Correct 31 ms 5968 KB Correct.
6 Correct 9 ms 8792 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 31384 KB Correct.
2 Correct 194 ms 6224 KB Correct.
3 Correct 179 ms 6504 KB Correct.
4 Correct 191 ms 6480 KB Correct.
5 Correct 217 ms 6100 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6488 KB Correct.
2 Correct 29 ms 6744 KB Correct.
3 Correct 28 ms 6736 KB Correct.
4 Correct 29 ms 10520 KB Correct.
5 Correct 25 ms 5976 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6712 KB Correct.
2 Correct 25 ms 6488 KB Correct.
3 Correct 54 ms 39316 KB Correct.
4 Correct 22 ms 8660 KB Correct.
5 Correct 29 ms 5976 KB Correct.
6 Correct 26 ms 6492 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 6480 KB Correct.
2 Correct 43 ms 5972 KB Correct.
3 Correct 1038 ms 39740 KB Correct.
4 Correct 501 ms 15596 KB Correct.
5 Correct 1038 ms 27156 KB Correct.
6 Correct 432 ms 16468 KB Correct.
7 Correct 452 ms 15484 KB Correct.
8 Correct 353 ms 8616 KB Correct.
9 Correct 191 ms 6476 KB Correct.
10 Correct 165 ms 6604 KB Correct.
11 Correct 356 ms 7504 KB Correct.
12 Correct 200 ms 6788 KB Correct.
13 Correct 191 ms 6700 KB Correct.
14 Correct 414 ms 18508 KB Correct.
15 Correct 396 ms 10352 KB Correct.
16 Correct 190 ms 6572 KB Correct.
17 Correct 220 ms 6952 KB Correct.
18 Correct 185 ms 6520 KB Correct.
19 Correct 513 ms 7600 KB Correct.
20 Correct 15 ms 5208 KB Correct.
21 Correct 15 ms 5548 KB Correct.
22 Correct 29 ms 6428 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 7480 KB Correct.
2 Correct 98 ms 7004 KB Correct.
3 Correct 2343 ms 101424 KB Correct.
4 Correct 587 ms 10576 KB Correct.
5 Correct 2663 ms 79016 KB Correct.
6 Correct 1074 ms 37612 KB Correct.
7 Correct 976 ms 23132 KB Correct.
8 Correct 581 ms 8368 KB Correct.
9 Correct 459 ms 7352 KB Correct.
10 Correct 434 ms 7468 KB Correct.
11 Correct 463 ms 6384 KB Correct.
12 Correct 514 ms 7636 KB Correct.
13 Correct 505 ms 7488 KB Correct.
14 Correct 2659 ms 43652 KB Correct.
15 Correct 2571 ms 51792 KB Correct.
16 Correct 771 ms 20220 KB Correct.
17 Correct 641 ms 10220 KB Correct.
18 Correct 462 ms 7440 KB Correct.
19 Correct 556 ms 7552 KB Correct.
20 Correct 481 ms 7752 KB Correct.
21 Correct 1321 ms 8444 KB Correct.
22 Correct 33 ms 5208 KB Correct.
23 Correct 37 ms 5960 KB Correct.
24 Correct 57 ms 8280 KB Correct.