oj.uz

Submission #1001073

# Submission time Handle Problem Language Result Execution time Memory
1001073 2024-06-18T14:08:57 Z ALTAKEXE Race (IOI11_race) C++17
31 / 100
 430 ms 192084 KB 
#include <bits/stdc++.h>
using namespace std;
int k, mn = INT_MAX;
vector<vector<int>> dp(200001,vector<int>(101,INT_MAX));
vector<pair<int, int>> adj[200001];
vector<vector<pair<int, int>>> path;
void dfs(int v, int p)
{
  dp[v][0] = 0;
  for (auto [i, w] : adj[v])
    if (i != p)
      dfs(i, v);
  path.assign(k + 1, {});
  for (auto [i, w] : adj[v])
  {
    if (i == p)
      continue;
    for (int j = w; j <= k; j++)
    {
      if (dp[i][j - w] == INT_MAX)
        continue;
      if (path[j].size() < 2)
        path[j].push_back({dp[i][j - w] + 1, i});
      else if (dp[i][j - w] + 1 < path[j][1].first)
        path[j][1] = {dp[i][j - w] + 1, i};
      if (path[j].size() == 2 && path[j][0].first > path[j][1].first)
        swap(path[j][0], path[j][1]);
      dp[v][j] = min(dp[v][j], dp[i][j - w] + 1);
    }
  }
  if (!path[k].empty())
    mn = min(mn, path[k][0].first);
  for (int i = 1; i < k; i++)
  {
    if (path[i].empty() || path[k - i].empty())
      continue;
    if (path[i][0].second != path[k - i][0].second)
      mn = min(mn, path[i][0].first + path[k - i][0].first);
    else if (1 < path[k - i].size())
      mn = min(mn, path[i][0].first + path[k - i][1].first);
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  for (int i = 0; i < N - 1; i++)
  {
    adj[H[i][0]].push_back({H[i][1], L[i]});
    adj[H[i][1]].push_back({H[i][0], L[i]});
  }
  dfs(0, -1);
  if (mn == INT_MAX)
    return -1;
  else
    return mn;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 94800 KB Output is correct
2 Correct 134 ms 94664 KB Output is correct
3 Correct 146 ms 94800 KB Output is correct
4 Correct 136 ms 94804 KB Output is correct
5 Correct 137 ms 94828 KB Output is correct
6 Correct 139 ms 94692 KB Output is correct
7 Correct 142 ms 94732 KB Output is correct
8 Correct 138 ms 94804 KB Output is correct
9 Correct 139 ms 94804 KB Output is correct
10 Correct 133 ms 94732 KB Output is correct
11 Correct 142 ms 94804 KB Output is correct
12 Correct 136 ms 94800 KB Output is correct
13 Correct 138 ms 94800 KB Output is correct
14 Correct 138 ms 94804 KB Output is correct
15 Correct 137 ms 94668 KB Output is correct
16 Correct 135 ms 94804 KB Output is correct
17 Correct 137 ms 94800 KB Output is correct
18 Correct 136 ms 94800 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 94800 KB Output is correct
2 Correct 134 ms 94664 KB Output is correct
3 Correct 146 ms 94800 KB Output is correct
4 Correct 136 ms 94804 KB Output is correct
5 Correct 137 ms 94828 KB Output is correct
6 Correct 139 ms 94692 KB Output is correct
7 Correct 142 ms 94732 KB Output is correct
8 Correct 138 ms 94804 KB Output is correct
9 Correct 139 ms 94804 KB Output is correct
10 Correct 133 ms 94732 KB Output is correct
11 Correct 142 ms 94804 KB Output is correct
12 Correct 136 ms 94800 KB Output is correct
13 Correct 138 ms 94800 KB Output is correct
14 Correct 138 ms 94804 KB Output is correct
15 Correct 137 ms 94668 KB Output is correct
16 Correct 135 ms 94804 KB Output is correct
17 Correct 137 ms 94800 KB Output is correct
18 Correct 136 ms 94800 KB Output is correct
19 Correct 131 ms 94804 KB Output is correct
20 Correct 149 ms 94804 KB Output is correct
21 Runtime error 208 ms 192084 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 94800 KB Output is correct
2 Correct 134 ms 94664 KB Output is correct
3 Correct 146 ms 94800 KB Output is correct
4 Correct 136 ms 94804 KB Output is correct
5 Correct 137 ms 94828 KB Output is correct
6 Correct 139 ms 94692 KB Output is correct
7 Correct 142 ms 94732 KB Output is correct
8 Correct 138 ms 94804 KB Output is correct
9 Correct 139 ms 94804 KB Output is correct
10 Correct 133 ms 94732 KB Output is correct
11 Correct 142 ms 94804 KB Output is correct
12 Correct 136 ms 94800 KB Output is correct
13 Correct 138 ms 94800 KB Output is correct
14 Correct 138 ms 94804 KB Output is correct
15 Correct 137 ms 94668 KB Output is correct
16 Correct 135 ms 94804 KB Output is correct
17 Correct 137 ms 94800 KB Output is correct
18 Correct 136 ms 94800 KB Output is correct
19 Correct 237 ms 100688 KB Output is correct
20 Correct 241 ms 101760 KB Output is correct
21 Correct 246 ms 101524 KB Output is correct
22 Correct 229 ms 101972 KB Output is correct
23 Correct 224 ms 102232 KB Output is correct
24 Correct 220 ms 102220 KB Output is correct
25 Correct 328 ms 108628 KB Output is correct
26 Correct 277 ms 114860 KB Output is correct
27 Correct 316 ms 106124 KB Output is correct
28 Correct 352 ms 133060 KB Output is correct
29 Correct 330 ms 131400 KB Output is correct
30 Correct 333 ms 106780 KB Output is correct
31 Correct 307 ms 106836 KB Output is correct
32 Correct 348 ms 106824 KB Output is correct
33 Correct 430 ms 105812 KB Output is correct
34 Correct 286 ms 106324 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 94800 KB Output is correct
2 Correct 134 ms 94664 KB Output is correct
3 Correct 146 ms 94800 KB Output is correct
4 Correct 136 ms 94804 KB Output is correct
5 Correct 137 ms 94828 KB Output is correct
6 Correct 139 ms 94692 KB Output is correct
7 Correct 142 ms 94732 KB Output is correct
8 Correct 138 ms 94804 KB Output is correct
9 Correct 139 ms 94804 KB Output is correct
10 Correct 133 ms 94732 KB Output is correct
11 Correct 142 ms 94804 KB Output is correct
12 Correct 136 ms 94800 KB Output is correct
13 Correct 138 ms 94800 KB Output is correct
14 Correct 138 ms 94804 KB Output is correct
15 Correct 137 ms 94668 KB Output is correct
16 Correct 135 ms 94804 KB Output is correct
17 Correct 137 ms 94800 KB Output is correct
18 Correct 136 ms 94800 KB Output is correct
19 Correct 131 ms 94804 KB Output is correct
20 Correct 149 ms 94804 KB Output is correct
21 Runtime error 208 ms 192084 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -