oj.uz

Submission #1009515

# Submission time Handle Problem Language Result Execution time Memory
1009515 2024-06-27T15:18:55 Z Muaath_5 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 94248 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,avx,sse3,sse4")
#define F first
#define S second
#define pii pair<int, int>
using namespace std;
const int mxN = 100000;
const double inf = 1000000000000000000;
struct path
{
  int i, k;
  double val;
};
bool operator<(const path &a, const path &b)
{
  return a.val < b.val;
}
bool operator>(const path &a, const path &b)
{
  return a.val > b.val;
}
double dp[mxN][69]; 
vector<pii> v[mxN];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
  for (int i = 0; i < N; i++)
    v[i].clear();
  K = min(K,68);
  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(arr[u.i] == 2 && u.k != K && 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 14 ms 4696 KB Correct.
2 Correct 14 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4700 KB Correct.
2 Correct 20 ms 4700 KB Correct.
3 Correct 16 ms 4836 KB Correct.
4 Correct 17 ms 4696 KB Correct.
5 Correct 18 ms 4700 KB Correct.
6 Correct 17 ms 9488 KB Correct.
7 Correct 22 ms 9564 KB Correct.
8 Correct 11 ms 16220 KB Correct.
9 Correct 15 ms 4700 KB Correct.
10 Correct 15 ms 4700 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4700 KB Correct.
2 Correct 20 ms 4700 KB Correct.
3 Correct 18 ms 4900 KB Correct.
4 Correct 18 ms 4792 KB Correct.
5 Correct 17 ms 4700 KB Correct.
6 Correct 7 ms 9308 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 39004 KB Correct.
2 Correct 435 ms 4700 KB Correct.
3 Correct 333 ms 4784 KB Correct.
4 Correct 367 ms 4700 KB Correct.
5 Correct 288 ms 4776 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4700 KB Correct.
2 Correct 17 ms 4696 KB Correct.
3 Correct 16 ms 4696 KB Correct.
4 Correct 22 ms 9564 KB Correct.
5 Correct 14 ms 4700 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4700 KB Correct.
2 Correct 15 ms 4844 KB Correct.
3 Correct 35 ms 48844 KB Correct.
4 Correct 12 ms 7512 KB Correct.
5 Correct 17 ms 4700 KB Correct.
6 Correct 18 ms 4700 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 5308 KB Correct.
2 Correct 37 ms 5600 KB Correct.
3 Correct 1240 ms 61520 KB Correct.
4 Correct 1051 ms 16588 KB Correct.
5 Correct 702 ms 62204 KB Correct.
6 Correct 292 ms 31292 KB Correct.
7 Correct 934 ms 19064 KB Correct.
8 Correct 894 ms 5444 KB Correct.
9 Correct 237 ms 5552 KB Correct.
10 Correct 240 ms 5556 KB Correct.
11 Correct 830 ms 5148 KB Correct.
12 Correct 264 ms 5456 KB Correct.
13 Correct 269 ms 5588 KB Correct.
14 Correct 740 ms 33124 KB Correct.
15 Correct 1057 ms 11868 KB Correct.
16 Correct 244 ms 5764 KB Correct.
17 Correct 287 ms 5344 KB Correct.
18 Correct 289 ms 5476 KB Correct.
19 Correct 855 ms 5660 KB Correct.
20 Correct 20 ms 4700 KB Correct.
21 Correct 24 ms 5216 KB Correct.
22 Correct 26 ms 6356 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 6676 KB Correct.
2 Correct 96 ms 6744 KB Correct.
3 Correct 418 ms 63060 KB Correct.
4 Correct 2334 ms 8852 KB Correct.
5 Correct 2058 ms 94248 KB Correct.
6 Correct 765 ms 45736 KB Correct.
7 Execution timed out 3062 ms 27432 KB Time limit exceeded
8 Halted 0 ms 0 KB -