oj.uz

Submission #1009486

# Submission time Handle Problem Language Result Execution time Memory
1009486 2024-06-27T14:59:49 Z Muaath_5 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 72652 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
#define all(v) ((v).begin(), (v).end())
#define F first
#define S second
typedef long long ll;
#define pii pair<ll, double>
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 2e5 + 5;
const double inf = 1e18;
struct path
{
  ll 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;
}
vector<vector<double>>dp; 
vector<int>vis;
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();
  vis.clear();
  dp.clear();
  dp.resize(N + 3);
  vis.resize(N + 3);
  v.resize(N + 3);
  K = min(K,70);
  for (int i = 0; i < M; i++)
  {
    v[x[i]].push_back({y[i], (double)c[i]});
    v[y[i]].push_back({x[i], (double)c[i]});
  }
  for(int i = 0;i < N;i++){
    dp[i].resize(K + 3);
    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 15 ms 860 KB Correct.
2 Correct 20 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1628 KB Correct.
2 Correct 23 ms 1532 KB Correct.
3 Correct 22 ms 1616 KB Correct.
4 Correct 24 ms 1564 KB Correct.
5 Correct 26 ms 1580 KB Correct.
6 Correct 25 ms 4800 KB Correct.
7 Correct 28 ms 4696 KB Correct.
8 Correct 15 ms 8796 KB Correct.
9 Correct 22 ms 1116 KB Correct.
10 Correct 22 ms 1292 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1608 KB Correct.
2 Correct 25 ms 1520 KB Correct.
3 Correct 24 ms 1540 KB Correct.
4 Correct 22 ms 1116 KB Correct.
5 Correct 32 ms 1080 KB Correct.
6 Correct 7 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 24512 KB Correct.
2 Correct 538 ms 1488 KB Correct.
3 Correct 490 ms 1548 KB Correct.
4 Correct 489 ms 1532 KB Correct.
5 Correct 370 ms 1112 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1500 KB Correct.
2 Correct 28 ms 1672 KB Correct.
3 Correct 21 ms 1488 KB Correct.
4 Correct 26 ms 4616 KB Correct.
5 Correct 17 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1628 KB Correct.
2 Correct 18 ms 1460 KB Correct.
3 Correct 42 ms 31980 KB Correct.
4 Correct 15 ms 3552 KB Correct.
5 Correct 18 ms 1116 KB Correct.
6 Correct 19 ms 1560 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 2228 KB Correct.
2 Correct 44 ms 2332 KB Correct.
3 Correct 1470 ms 32496 KB Correct.
4 Correct 1341 ms 9076 KB Correct.
5 Correct 952 ms 68288 KB Correct.
6 Correct 396 ms 36012 KB Correct.
7 Correct 1259 ms 8688 KB Correct.
8 Correct 1138 ms 2644 KB Correct.
9 Correct 340 ms 2272 KB Correct.
10 Correct 330 ms 2664 KB Correct.
11 Correct 1095 ms 2260 KB Correct.
12 Correct 348 ms 2172 KB Correct.
13 Correct 351 ms 2332 KB Correct.
14 Correct 988 ms 11936 KB Correct.
15 Correct 1346 ms 5032 KB Correct.
16 Correct 315 ms 2620 KB Correct.
17 Correct 406 ms 2268 KB Correct.
18 Correct 362 ms 2232 KB Correct.
19 Correct 1124 ms 3372 KB Correct.
20 Correct 25 ms 728 KB Correct.
21 Correct 30 ms 1192 KB Correct.
22 Correct 38 ms 3032 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 4544 KB Correct.
2 Correct 127 ms 4208 KB Correct.
3 Correct 610 ms 72652 KB Correct.
4 Execution timed out 3067 ms 5908 KB Time limit exceeded
5 Halted 0 ms 0 KB -