oj.uz

Submission #954116

# Submission time Handle Problem Language Result Execution time Memory
954116 2024-03-27T10:00:46 Z Otalp Cyberland (APIO23_cyberland) C++17
100 / 100
 2735 ms 142164 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second


vector<pair<int, int>> q[200100];
double dp[200100][105];
int us[200100][105];
int pos[200100];
int H;

void dfs(int v){
  pos[v] = 1;
  if(v == H) return;
  for(int i=0; i<q[v].size(); i++){
    int to = q[v][i].ff;
    if(pos[to]) continue;
    dfs(to);
  }
}

double st[200];


double solve(int n, int m, int K, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
  H = h;
  int k = min(K, 44);
  for(int i=0; i<n; i++){
    q[i].clear();
    for(int j=0; j<=k; j++){
      dp[i][j] = us[i][j] = 0;
    }
    pos[i] = 0;
  }
  for(int i=0; i<m; i++){
    q[x[i]].pb({y[i], c[i]});
    q[y[i]].pb({x[i], c[i]});
  }
  st[0]= 1;
  for(int i=1; i<=k + 2; i++){
    st[i] = st[i - 1] / 2;
  }

  dfs(0);

  if(pos[h] == 0) return -1; 
  set<pair<pair<int, double>, int>> s;
  s.insert({{0, 0}, h});

  while(s.size()){
    auto it = s.begin();
    if(us[it -> ss][it -> ff.ff]){
      s.erase(it);
      continue;
    }
    int v = it -> ss;
    int c = it -> ff.ff;
    us[v][c] = 1;
    dp[v][c] = it -> ff.ss;
    s.erase(it);
    for(int i=0; i<q[v].size(); i++){
      int to = q[v][i].ff;
      int x = q[v][i].ss;
      if(!us[to][c] and to != h){
        s.insert({{c, dp[v][c] + x * st[c]}, to});
      }
      if(arr[to] == 2 and c + 1 <= k and !us[to][c+1] and to != h){
        s.insert({{c + 1, dp[v][c] + x * st[c]}, to});
      }
    }
  }
  double mn=1e18;
  if(k < K){
    for(int i=0; i<n; i++){
      if(us[i][k] and pos[i]) mn = min(mn, dp[i][k]);
    }
  }
  arr[0] = 0;
  for(int i=0; i<n; i++){
    if(pos[i] and arr[i] == 0){
      for(int j=0; j<=k; j++){
        if(us[i][j]) mn = min(mn, dp[i][j]);
      }
    }
  }
  if(mn == 1e18) return -1;
  return mn;
}

Compilation message

cyberland.cpp: In function 'void dfs(int)':
cyberland.cpp:19:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(int i=0; i<q[v].size(); i++){
      |                ~^~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0; i<q[v].size(); i++){
      |                  ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10432 KB Correct.
2 Correct 19 ms 10332 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10332 KB Correct.
2 Correct 27 ms 10332 KB Correct.
3 Correct 25 ms 10332 KB Correct.
4 Correct 26 ms 10448 KB Correct.
5 Correct 25 ms 10328 KB Correct.
6 Correct 26 ms 23384 KB Correct.
7 Correct 32 ms 23388 KB Correct.
8 Correct 24 ms 36444 KB Correct.
9 Correct 24 ms 10328 KB Correct.
10 Correct 23 ms 10332 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10332 KB Correct.
2 Correct 26 ms 10436 KB Correct.
3 Correct 24 ms 10332 KB Correct.
4 Correct 29 ms 10376 KB Correct.
5 Correct 25 ms 10328 KB Correct.
6 Correct 8 ms 19036 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 87228 KB Correct.
2 Correct 235 ms 10332 KB Correct.
3 Correct 217 ms 10632 KB Correct.
4 Correct 222 ms 10332 KB Correct.
5 Correct 191 ms 10352 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10588 KB Correct.
2 Correct 26 ms 10528 KB Correct.
3 Correct 25 ms 10332 KB Correct.
4 Correct 29 ms 23644 KB Correct.
5 Correct 21 ms 10332 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10332 KB Correct.
2 Correct 22 ms 10424 KB Correct.
3 Correct 56 ms 106068 KB Correct.
4 Correct 20 ms 19288 KB Correct.
5 Correct 23 ms 10332 KB Correct.
6 Correct 24 ms 10332 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 10576 KB Correct.
2 Correct 58 ms 12708 KB Correct.
3 Correct 681 ms 131664 KB Correct.
4 Correct 325 ms 36876 KB Correct.
5 Correct 1867 ms 67408 KB Correct.
6 Correct 1654 ms 36248 KB Correct.
7 Correct 327 ms 40788 KB Correct.
8 Correct 274 ms 12892 KB Correct.
9 Correct 269 ms 10572 KB Correct.
10 Correct 235 ms 10576 KB Correct.
11 Correct 244 ms 10580 KB Correct.
12 Correct 270 ms 10544 KB Correct.
13 Correct 304 ms 10832 KB Correct.
14 Correct 333 ms 68372 KB Correct.
15 Correct 316 ms 25680 KB Correct.
16 Correct 275 ms 10552 KB Correct.
17 Correct 314 ms 10580 KB Correct.
18 Correct 287 ms 10652 KB Correct.
19 Correct 527 ms 10516 KB Correct.
20 Correct 15 ms 10332 KB Correct.
21 Correct 19 ms 10328 KB Correct.
22 Correct 103 ms 11868 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 10584 KB Correct.
2 Correct 83 ms 12720 KB Correct.
3 Correct 644 ms 142164 KB Correct.
4 Correct 324 ms 16976 KB Correct.
5 Correct 2735 ms 67412 KB Correct.
6 Correct 2177 ms 36248 KB Correct.
7 Correct 445 ms 56764 KB Correct.
8 Correct 300 ms 10656 KB Correct.
9 Correct 377 ms 10576 KB Correct.
10 Correct 343 ms 10580 KB Correct.
11 Correct 196 ms 11368 KB Correct.
12 Correct 380 ms 10452 KB Correct.
13 Correct 428 ms 10832 KB Correct.
14 Correct 1135 ms 60540 KB Correct.
15 Correct 929 ms 72128 KB Correct.
16 Correct 453 ms 32388 KB Correct.
17 Correct 336 ms 14740 KB Correct.
18 Correct 410 ms 11716 KB Correct.
19 Correct 458 ms 11504 KB Correct.
20 Correct 415 ms 11664 KB Correct.
21 Correct 754 ms 12372 KB Correct.
22 Correct 22 ms 10328 KB Correct.
23 Correct 27 ms 10332 KB Correct.
24 Correct 149 ms 12008 KB Correct.