oj.uz

Submission #1009500

# Submission time Handle Problem Language Result Execution time Memory
1009500 2024-06-27T15:10:34 Z Muaath_5 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 92320 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,avx,sse3,sse4")
#define all(v) ((v).begin(), (v).end())
#define F first
#define S second
typedef long long ll;
#define pii pair<int, int>
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 1e5 + 5;
const double inf = 1e18;
struct path
{
  int i, k;
  double val;
};
bool operator<(path a, path b)
{
  return a.val < b.val;
}
bool operator>(path a, path b)
{
  return a.val > b.val;
}
double dp[mxN][71]; 
vector<vector<pii>> v;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
  v.clear();
  v.resize(N + 3);
  K = min(K,70);
  for (int i = 0; i < M; i++)
  {
    v[x[i]].push_back({y[i], c[i]});
    v[y[i]].push_back({x[i], c[i]});
  }
  for(int i = 0;i < N;i++)
    for(int j = 0;j <= K;j++)
      dp[i][j] = inf;
  priority_queue<path,vector<path>,greater<path>>q;
  q.push({0,0,0});
  dp[0][0] = 0;
  while(q.size()){
    const auto u = q.top();
    q.pop();
    if(u.val < dp[u.i][u.k] || u.i == H) continue;
    for(const auto &x : v[u.i]){
      if (arr[x.F] == 0 && dp[x.F][u.k] != (double)0)
      {
        dp[x.F][u.k] = (double)0;
        q.push({x.F, u.k, (double)0});
      }
      if(dp[x.F][u.k] > dp[u.i][u.k] + x.S){
        dp[x.F][u.k] = dp[u.i][u.k] + x.S;
        q.push({x.F,u.k,dp[x.F][u.k]});
      }
      if(u.k != K && arr[u.i] == 2 && dp[x.F][u.k + 1] > dp[u.i][u.k] / 2 + x.S){
        dp[x.F][u.k + 1] = dp[u.i][u.k] / 2 + x.S;
        q.push({x.F,u.k + 1,dp[x.F][u.k + 1]});
      }
    }
  }
  double ans = inf;
  for(int i = 0;i <= K;i++){
    ans = min(ans,dp[H][i]);
  }
  return ans == inf ? -1 : ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 604 KB Correct.
2 Correct 12 ms 492 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Correct.
2 Correct 18 ms 2652 KB Correct.
3 Correct 26 ms 2652 KB Correct.
4 Correct 18 ms 2652 KB Correct.
5 Correct 17 ms 2652 KB Correct.
6 Correct 16 ms 7772 KB Correct.
7 Correct 23 ms 7768 KB Correct.
8 Correct 11 ms 14680 KB Correct.
9 Correct 19 ms 564 KB Correct.
10 Correct 15 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2648 KB Correct.
2 Correct 22 ms 2648 KB Correct.
3 Correct 19 ms 2748 KB Correct.
4 Correct 22 ms 348 KB Correct.
5 Correct 17 ms 344 KB Correct.
6 Correct 4 ms 7512 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 38496 KB Correct.
2 Correct 421 ms 2760 KB Correct.
3 Correct 367 ms 2784 KB Correct.
4 Correct 410 ms 2768 KB Correct.
5 Correct 293 ms 348 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2780 KB Correct.
2 Correct 18 ms 2652 KB Correct.
3 Correct 19 ms 2648 KB Correct.
4 Correct 24 ms 7772 KB Correct.
5 Correct 15 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2648 KB Correct.
2 Correct 23 ms 2792 KB Correct.
3 Correct 36 ms 50580 KB Correct.
4 Correct 12 ms 5464 KB Correct.
5 Correct 16 ms 348 KB Correct.
6 Correct 18 ms 2652 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 3272 KB Correct.
2 Correct 35 ms 3548 KB Correct.
3 Correct 1183 ms 62992 KB Correct.
4 Correct 997 ms 15020 KB Correct.
5 Correct 686 ms 61360 KB Correct.
6 Correct 299 ms 27568 KB Correct.
7 Correct 928 ms 17416 KB Correct.
8 Correct 939 ms 3180 KB Correct.
9 Correct 245 ms 3520 KB Correct.
10 Correct 278 ms 3568 KB Correct.
11 Correct 880 ms 3224 KB Correct.
12 Correct 261 ms 3428 KB Correct.
13 Correct 263 ms 3480 KB Correct.
14 Correct 802 ms 32292 KB Correct.
15 Correct 1079 ms 10068 KB Correct.
16 Correct 247 ms 3504 KB Correct.
17 Correct 318 ms 3284 KB Correct.
18 Correct 291 ms 3548 KB Correct.
19 Correct 838 ms 3684 KB Correct.
20 Correct 23 ms 600 KB Correct.
21 Correct 24 ms 3172 KB Correct.
22 Correct 27 ms 4308 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 4692 KB Correct.
2 Correct 86 ms 4720 KB Correct.
3 Correct 393 ms 64488 KB Correct.
4 Correct 2328 ms 6972 KB Correct.
5 Correct 2041 ms 92320 KB Correct.
6 Correct 869 ms 45484 KB Correct.
7 Execution timed out 3062 ms 25972 KB Time limit exceeded
8 Halted 0 ms 0 KB -