oj.uz

답안 #1009491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009491 2024-06-27T15:02:47 Z Muaath_5 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 78504 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 = 1e5 + 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;
}
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], (double)c[i]});
    v[y[i]].push_back({x[i], (double)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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 604 KB Correct.
2 Correct 14 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2652 KB Correct.
2 Correct 20 ms 2652 KB Correct.
3 Correct 19 ms 2832 KB Correct.
4 Correct 20 ms 2904 KB Correct.
5 Correct 20 ms 2652 KB Correct.
6 Correct 19 ms 7840 KB Correct.
7 Correct 25 ms 7836 KB Correct.
8 Correct 13 ms 15112 KB Correct.
9 Correct 17 ms 344 KB Correct.
10 Correct 16 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2652 KB Correct.
2 Correct 22 ms 2652 KB Correct.
3 Correct 21 ms 2648 KB Correct.
4 Correct 21 ms 344 KB Correct.
5 Correct 19 ms 552 KB Correct.
6 Correct 5 ms 7516 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 39404 KB Correct.
2 Correct 496 ms 2652 KB Correct.
3 Correct 451 ms 2784 KB Correct.
4 Correct 493 ms 2652 KB Correct.
5 Correct 369 ms 580 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2652 KB Correct.
2 Correct 20 ms 2848 KB Correct.
3 Correct 21 ms 2652 KB Correct.
4 Correct 20 ms 8152 KB Correct.
5 Correct 15 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2648 KB Correct.
2 Correct 18 ms 2856 KB Correct.
3 Correct 46 ms 51848 KB Correct.
4 Correct 13 ms 5724 KB Correct.
5 Correct 17 ms 344 KB Correct.
6 Correct 19 ms 2652 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 359 ms 3496 KB Correct.
2 Correct 42 ms 4092 KB Correct.
3 Correct 1420 ms 64764 KB Correct.
4 Correct 1214 ms 15320 KB Correct.
5 Correct 871 ms 78504 KB Correct.
6 Correct 361 ms 37816 KB Correct.
7 Correct 1179 ms 17856 KB Correct.
8 Correct 1088 ms 3268 KB Correct.
9 Correct 293 ms 3768 KB Correct.
10 Correct 307 ms 3864 KB Correct.
11 Correct 1069 ms 3288 KB Correct.
12 Correct 308 ms 3756 KB Correct.
13 Correct 318 ms 3856 KB Correct.
14 Correct 864 ms 33872 KB Correct.
15 Correct 1275 ms 10100 KB Correct.
16 Correct 318 ms 3944 KB Correct.
17 Correct 395 ms 3560 KB Correct.
18 Correct 375 ms 3880 KB Correct.
19 Correct 1142 ms 4068 KB Correct.
20 Correct 24 ms 600 KB Correct.
21 Correct 29 ms 3404 KB Correct.
22 Correct 31 ms 4820 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1051 ms 5528 KB Correct.
2 Correct 122 ms 5656 KB Correct.
3 Correct 486 ms 66028 KB Correct.
4 Execution timed out 3040 ms 7964 KB Time limit exceeded
5 Halted 0 ms 0 KB -