oj.uz

Submission #1009506

# Submission time Handle Problem Language Result Execution time Memory
1009506 2024-06-27T15:13:45 Z Muaath_5 Cyberland (APIO23_cyberland) C++17
97 / 100
 1182 ms 66484 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, double>
    using namespace std;
    const ll mod = 1e9 + 7;
    const ll mxN = 100000;
    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,65);
      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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2652 KB Correct.
2 Correct 16 ms 2652 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4696 KB Correct.
2 Correct 17 ms 4700 KB Correct.
3 Correct 17 ms 4860 KB Correct.
4 Correct 18 ms 4700 KB Correct.
5 Correct 18 ms 4700 KB Correct.
6 Correct 17 ms 9888 KB Correct.
7 Correct 21 ms 9936 KB Correct.
8 Correct 10 ms 16988 KB Correct.
9 Correct 17 ms 2612 KB Correct.
10 Correct 15 ms 2396 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4700 KB Correct.
2 Correct 20 ms 4700 KB Correct.
3 Correct 18 ms 4700 KB Correct.
4 Correct 18 ms 2612 KB Correct.
5 Correct 18 ms 2392 KB Correct.
6 Correct 5 ms 9564 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 41372 KB Correct.
2 Correct 354 ms 4876 KB Correct.
3 Correct 272 ms 4696 KB Correct.
4 Correct 311 ms 4700 KB Correct.
5 Correct 217 ms 2640 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4700 KB Correct.
2 Correct 18 ms 4700 KB Correct.
3 Correct 19 ms 4700 KB Correct.
4 Correct 19 ms 9820 KB Correct.
5 Correct 17 ms 2396 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4696 KB Correct.
2 Correct 15 ms 4696 KB Correct.
3 Correct 32 ms 53904 KB Correct.
4 Correct 12 ms 7772 KB Correct.
5 Correct 19 ms 2608 KB Correct.
6 Correct 16 ms 4916 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 5332 KB Correct.
2 Correct 32 ms 5608 KB Correct.
3 Correct 1182 ms 66484 KB Correct.
4 Correct 924 ms 17352 KB Correct.
5 Correct 717 ms 64936 KB Correct.
6 Correct 297 ms 31412 KB Correct.
7 Correct 864 ms 19944 KB Correct.
8 Correct 750 ms 5232 KB Correct.
9 Correct 219 ms 5568 KB Correct.
10 Correct 220 ms 5604 KB Correct.
11 Correct 673 ms 4944 KB Correct.
12 Correct 218 ms 5472 KB Correct.
13 Correct 213 ms 5624 KB Correct.
14 Correct 719 ms 34884 KB Correct.
15 Correct 876 ms 12228 KB Correct.
16 Correct 204 ms 5564 KB Correct.
17 Correct 255 ms 5312 KB Correct.
18 Correct 244 ms 5520 KB Correct.
19 Correct 738 ms 5648 KB Correct.
20 Correct 16 ms 2652 KB Correct.
21 Correct 24 ms 5212 KB Correct.
22 Correct 25 ms 6356 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 6628 KB Correct.
2 Correct 87 ms 6832 KB Correct.
3 Incorrect 311 ms 66128 KB Wrong Answer.
4 Halted 0 ms 0 KB -