oj.uz

Submission #958740

# Submission time Handle Problem Language Result Execution time Memory
958740 2024-04-06T13:19:25 Z ALTAKEXE Cyberland (APIO23_cyberland) C++17
100 / 100
 1886 ms 172100 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f first
#define s second
#define inf 1e18
#define dinf 1e-9
using namespace std;
vector<array<ll, 2>> adj[100000];
ll h;
bool visited[100000];
priority_queue<array<ld, 2>, vector<array<ld, 2>>, greater<array<ld, 2>>> pq[101];
ld dp[100000][101], ep = dinf;

void dfs(ll u)
{
  visited[u] = 1;
  for (auto [v, x] : adj[u])
  {
    if (v != h && !visited[v])
    {
      dfs(v);
    }
  }
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr)
{
  K = min(K, 80), h = H;
  for (int i = 0; i < N; ++i)
  {
    visited[i] = 0;
    adj[i].clear();
    for (int j = 0; j <= K; ++j)
    {
      dp[i][j] = 1e18;
    }
  }
  for (int i = 0; i < M; ++i)
  {
    adj[x[i]].push_back({y[i], c[i]});
    adj[y[i]].push_back({x[i], c[i]});
  }
  dfs(0);
  for (int i = 0; i < N; ++i)
  {
    if (visited[i] && (!arr[i] || !i))
    {
      dp[i][K] = 0;
      pq[K].push({0, (ld)i});
    }
  }
  for (int i = K; i >= 0; --i)
  {
    while (!pq[i].empty())
    {
      auto [w, du] = pq[i].top();
      pq[i].pop();
      ll u = (ll)du;
      if (dp[u][i] != w || u == H)
        continue;
      for (auto [v, x] : adj[u])
      {
        if (dp[v][i] - (w + (ld)x) > ep)
        {
          dp[v][i] = w + (ld)x;
          pq[i].push({dp[v][i], (ld)v});
        }
        if (i && arr[v] == 2 && (dp[v][i - 1] - (ld)(w + (ld)x) / 2) > ep)
        {
          dp[v][i - 1] = (w + (ld)x) / 2;
          pq[i - 1].push({dp[v][i - 1], (ld)v});
        }
      }
    }
  }
  ld f = inf;
  for (int i = 0; i <= K; ++i)
  {
    f = min(f, dp[H][i]);
  }
  if (f == inf)
    return -1;
  return f;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4952 KB Correct.
2 Correct 22 ms 4956 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7304 KB Correct.
2 Correct 34 ms 7308 KB Correct.
3 Correct 31 ms 7256 KB Correct.
4 Correct 32 ms 7512 KB Correct.
5 Correct 33 ms 7260 KB Correct.
6 Correct 34 ms 22416 KB Correct.
7 Correct 43 ms 22428 KB Correct.
8 Correct 21 ms 37468 KB Correct.
9 Correct 30 ms 5104 KB Correct.
10 Correct 30 ms 5104 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7260 KB Correct.
2 Correct 32 ms 7260 KB Correct.
3 Correct 31 ms 7256 KB Correct.
4 Correct 31 ms 5108 KB Correct.
5 Correct 33 ms 4956 KB Correct.
6 Correct 9 ms 20316 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 107604 KB Correct.
2 Correct 149 ms 7516 KB Correct.
3 Correct 137 ms 7512 KB Correct.
4 Correct 141 ms 7648 KB Correct.
5 Correct 89 ms 4956 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7260 KB Correct.
2 Correct 34 ms 7256 KB Correct.
3 Correct 29 ms 7364 KB Correct.
4 Correct 31 ms 22824 KB Correct.
5 Correct 29 ms 5108 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7256 KB Correct.
2 Correct 26 ms 7248 KB Correct.
3 Correct 70 ms 132436 KB Correct.
4 Correct 23 ms 18524 KB Correct.
5 Correct 29 ms 5076 KB Correct.
6 Correct 29 ms 7260 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 8016 KB Correct.
2 Correct 28 ms 10076 KB Correct.
3 Correct 850 ms 168332 KB Correct.
4 Correct 404 ms 42928 KB Correct.
5 Correct 749 ms 98236 KB Correct.
6 Correct 290 ms 46664 KB Correct.
7 Correct 423 ms 47156 KB Correct.
8 Correct 284 ms 12232 KB Correct.
9 Correct 156 ms 7844 KB Correct.
10 Correct 144 ms 7772 KB Correct.
11 Correct 252 ms 7508 KB Correct.
12 Correct 170 ms 7764 KB Correct.
13 Correct 164 ms 8072 KB Correct.
14 Correct 395 ms 85404 KB Correct.
15 Correct 338 ms 27476 KB Correct.
16 Correct 161 ms 8040 KB Correct.
17 Correct 182 ms 7760 KB Correct.
18 Correct 172 ms 7848 KB Correct.
19 Correct 440 ms 7984 KB Correct.
20 Correct 10 ms 4968 KB Correct.
21 Correct 13 ms 7516 KB Correct.
22 Correct 24 ms 9820 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 8636 KB Correct.
2 Correct 67 ms 11356 KB Correct.
3 Correct 1382 ms 172100 KB Correct.
4 Correct 425 ms 17280 KB Correct.
5 Correct 1806 ms 145548 KB Correct.
6 Correct 700 ms 77436 KB Correct.
7 Correct 808 ms 77728 KB Correct.
8 Correct 386 ms 10104 KB Correct.
9 Correct 352 ms 9516 KB Correct.
10 Correct 324 ms 9436 KB Correct.
11 Correct 272 ms 6388 KB Correct.
12 Correct 375 ms 9484 KB Correct.
13 Correct 367 ms 9704 KB Correct.
14 Correct 1886 ms 107828 KB Correct.
15 Correct 1683 ms 94684 KB Correct.
16 Correct 681 ms 41600 KB Correct.
17 Correct 437 ms 14108 KB Correct.
18 Correct 359 ms 9496 KB Correct.
19 Correct 414 ms 9760 KB Correct.
20 Correct 428 ms 9684 KB Correct.
21 Correct 1120 ms 10612 KB Correct.
22 Correct 21 ms 5212 KB Correct.
23 Correct 28 ms 8284 KB Correct.
24 Correct 55 ms 12928 KB Correct.