oj.uz

Submission #1002139

# Submission time Handle Problem Language Result Execution time Memory
1002139 2024-06-19T10:23:30 Z Tsog Race (IOI11_race) C++14
31 / 100
 395 ms 184652 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;
}

Compilation message

race.cpp: In function 'void dfs(int, int)':
race.cpp:10:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |   for (auto [i, w] : adj[v])
      |             ^
race.cpp:14:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |   for (auto [i, w] : adj[v])
      |             ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 91032 KB Output is correct
2 Correct 130 ms 91052 KB Output is correct
3 Correct 126 ms 91204 KB Output is correct
4 Correct 124 ms 91216 KB Output is correct
5 Correct 124 ms 91204 KB Output is correct
6 Correct 120 ms 91196 KB Output is correct
7 Correct 129 ms 91216 KB Output is correct
8 Correct 121 ms 91164 KB Output is correct
9 Correct 131 ms 91096 KB Output is correct
10 Correct 124 ms 91084 KB Output is correct
11 Correct 127 ms 91068 KB Output is correct
12 Correct 135 ms 91220 KB Output is correct
13 Correct 123 ms 91220 KB Output is correct
14 Correct 120 ms 91112 KB Output is correct
15 Correct 125 ms 91216 KB Output is correct
16 Correct 119 ms 91220 KB Output is correct
17 Correct 120 ms 91220 KB Output is correct
18 Correct 118 ms 91112 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 91032 KB Output is correct
2 Correct 130 ms 91052 KB Output is correct
3 Correct 126 ms 91204 KB Output is correct
4 Correct 124 ms 91216 KB Output is correct
5 Correct 124 ms 91204 KB Output is correct
6 Correct 120 ms 91196 KB Output is correct
7 Correct 129 ms 91216 KB Output is correct
8 Correct 121 ms 91164 KB Output is correct
9 Correct 131 ms 91096 KB Output is correct
10 Correct 124 ms 91084 KB Output is correct
11 Correct 127 ms 91068 KB Output is correct
12 Correct 135 ms 91220 KB Output is correct
13 Correct 123 ms 91220 KB Output is correct
14 Correct 120 ms 91112 KB Output is correct
15 Correct 125 ms 91216 KB Output is correct
16 Correct 119 ms 91220 KB Output is correct
17 Correct 120 ms 91220 KB Output is correct
18 Correct 118 ms 91112 KB Output is correct
19 Correct 123 ms 91220 KB Output is correct
20 Correct 120 ms 91220 KB Output is correct
21 Runtime error 188 ms 184652 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 126 ms 91032 KB Output is correct
2 Correct 130 ms 91052 KB Output is correct
3 Correct 126 ms 91204 KB Output is correct
4 Correct 124 ms 91216 KB Output is correct
5 Correct 124 ms 91204 KB Output is correct
6 Correct 120 ms 91196 KB Output is correct
7 Correct 129 ms 91216 KB Output is correct
8 Correct 121 ms 91164 KB Output is correct
9 Correct 131 ms 91096 KB Output is correct
10 Correct 124 ms 91084 KB Output is correct
11 Correct 127 ms 91068 KB Output is correct
12 Correct 135 ms 91220 KB Output is correct
13 Correct 123 ms 91220 KB Output is correct
14 Correct 120 ms 91112 KB Output is correct
15 Correct 125 ms 91216 KB Output is correct
16 Correct 119 ms 91220 KB Output is correct
17 Correct 120 ms 91220 KB Output is correct
18 Correct 118 ms 91112 KB Output is correct
19 Correct 220 ms 96132 KB Output is correct
20 Correct 229 ms 96992 KB Output is correct
21 Correct 223 ms 96596 KB Output is correct
22 Correct 228 ms 97364 KB Output is correct
23 Correct 218 ms 97612 KB Output is correct
24 Correct 211 ms 97384 KB Output is correct
25 Correct 292 ms 104404 KB Output is correct
26 Correct 245 ms 110160 KB Output is correct
27 Correct 314 ms 102732 KB Output is correct
28 Correct 351 ms 129360 KB Output is correct
29 Correct 349 ms 127704 KB Output is correct
30 Correct 307 ms 103248 KB Output is correct
31 Correct 313 ms 103508 KB Output is correct
32 Correct 331 ms 103252 KB Output is correct
33 Correct 395 ms 102604 KB Output is correct
34 Correct 267 ms 102736 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 91032 KB Output is correct
2 Correct 130 ms 91052 KB Output is correct
3 Correct 126 ms 91204 KB Output is correct
4 Correct 124 ms 91216 KB Output is correct
5 Correct 124 ms 91204 KB Output is correct
6 Correct 120 ms 91196 KB Output is correct
7 Correct 129 ms 91216 KB Output is correct
8 Correct 121 ms 91164 KB Output is correct
9 Correct 131 ms 91096 KB Output is correct
10 Correct 124 ms 91084 KB Output is correct
11 Correct 127 ms 91068 KB Output is correct
12 Correct 135 ms 91220 KB Output is correct
13 Correct 123 ms 91220 KB Output is correct
14 Correct 120 ms 91112 KB Output is correct
15 Correct 125 ms 91216 KB Output is correct
16 Correct 119 ms 91220 KB Output is correct
17 Correct 120 ms 91220 KB Output is correct
18 Correct 118 ms 91112 KB Output is correct
19 Correct 123 ms 91220 KB Output is correct
20 Correct 120 ms 91220 KB Output is correct
21 Runtime error 188 ms 184652 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -