oj.uz

Submission #1001682

# Submission time Handle Problem Language Result Execution time Memory
1001682 2024-06-19T06:57:26 Z nomuluun Race (IOI11_race) C++14
31 / 100
 410 ms 184716 KB 
#include <bits/stdc++.h>
using namespace std;
int k, mn = INT_MAX;
vector<vector<int>> dp(200001, vector<int>(101, INT_MAX)); // sum I and ends at node v is the minimum of the paths
vector<pair<int, int>> adj[200001];                        // save edges
vector<vector<pair<int, int>>> path;                       // keep the best paths of each weights
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}); // keep best two paths
      else if (dp[i][j - w] + 1 < path[j][1].first)
        path[j][1] = {dp[i][j - w] + 1, i}; // keep current path
      if (path[j].size() == 2 && path[j][0].first > path[j][1].first)
        swap(path[j][0], path[j][1]); // swap shortest path
      dp[v][j] = min(dp[v][j], dp[i][j - w] + 1);
    }
  }
  if (!path[k].empty())
    mn = min(mn, path[k][0].first); // if there is any path which is exactly K
  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); // compare 2 best paths
    else if (1 < path[k - i].size())
      mn = min(mn, path[i][0].first + path[k - i][1].first); // compare 2 best paths if there is path over 1.
  }
}
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;
}
#define MAX_N 500000

static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

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])
      |             ^
race.cpp: At global scope:
race.cpp:62:12: warning: 'solution' defined but not used [-Wunused-variable]
   62 | static int solution;
      |            ^~~~~~~~
race.cpp:61:12: warning: 'L' defined but not used [-Wunused-variable]
   61 | static int L[MAX_N];
      |            ^
race.cpp:60:12: warning: 'H' defined but not used [-Wunused-variable]
   60 | static int H[MAX_N][2];
      |            ^
race.cpp:59:15: warning: 'K' defined but not used [-Wunused-variable]
   59 | static int N, K;
      |               ^
race.cpp:59:12: warning: 'N' defined but not used [-Wunused-variable]
   59 | static int N, K;
      |            ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 91188 KB Output is correct
2 Correct 130 ms 91220 KB Output is correct
3 Correct 133 ms 91080 KB Output is correct
4 Correct 129 ms 91084 KB Output is correct
5 Correct 128 ms 91204 KB Output is correct
6 Correct 129 ms 91216 KB Output is correct
7 Correct 137 ms 91040 KB Output is correct
8 Correct 135 ms 91216 KB Output is correct
9 Correct 129 ms 91220 KB Output is correct
10 Correct 135 ms 91216 KB Output is correct
11 Correct 137 ms 91216 KB Output is correct
12 Correct 140 ms 91220 KB Output is correct
13 Correct 128 ms 91048 KB Output is correct
14 Correct 128 ms 91216 KB Output is correct
15 Correct 132 ms 91028 KB Output is correct
16 Correct 133 ms 91216 KB Output is correct
17 Correct 128 ms 91116 KB Output is correct
18 Correct 127 ms 91220 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 91188 KB Output is correct
2 Correct 130 ms 91220 KB Output is correct
3 Correct 133 ms 91080 KB Output is correct
4 Correct 129 ms 91084 KB Output is correct
5 Correct 128 ms 91204 KB Output is correct
6 Correct 129 ms 91216 KB Output is correct
7 Correct 137 ms 91040 KB Output is correct
8 Correct 135 ms 91216 KB Output is correct
9 Correct 129 ms 91220 KB Output is correct
10 Correct 135 ms 91216 KB Output is correct
11 Correct 137 ms 91216 KB Output is correct
12 Correct 140 ms 91220 KB Output is correct
13 Correct 128 ms 91048 KB Output is correct
14 Correct 128 ms 91216 KB Output is correct
15 Correct 132 ms 91028 KB Output is correct
16 Correct 133 ms 91216 KB Output is correct
17 Correct 128 ms 91116 KB Output is correct
18 Correct 127 ms 91220 KB Output is correct
19 Correct 130 ms 91216 KB Output is correct
20 Correct 134 ms 91220 KB Output is correct
21 Runtime error 195 ms 184716 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 91188 KB Output is correct
2 Correct 130 ms 91220 KB Output is correct
3 Correct 133 ms 91080 KB Output is correct
4 Correct 129 ms 91084 KB Output is correct
5 Correct 128 ms 91204 KB Output is correct
6 Correct 129 ms 91216 KB Output is correct
7 Correct 137 ms 91040 KB Output is correct
8 Correct 135 ms 91216 KB Output is correct
9 Correct 129 ms 91220 KB Output is correct
10 Correct 135 ms 91216 KB Output is correct
11 Correct 137 ms 91216 KB Output is correct
12 Correct 140 ms 91220 KB Output is correct
13 Correct 128 ms 91048 KB Output is correct
14 Correct 128 ms 91216 KB Output is correct
15 Correct 132 ms 91028 KB Output is correct
16 Correct 133 ms 91216 KB Output is correct
17 Correct 128 ms 91116 KB Output is correct
18 Correct 127 ms 91220 KB Output is correct
19 Correct 227 ms 95968 KB Output is correct
20 Correct 225 ms 95928 KB Output is correct
21 Correct 231 ms 96336 KB Output is correct
22 Correct 223 ms 96080 KB Output is correct
23 Correct 225 ms 96344 KB Output is correct
24 Correct 246 ms 96240 KB Output is correct
25 Correct 301 ms 102736 KB Output is correct
26 Correct 266 ms 109408 KB Output is correct
27 Correct 322 ms 100980 KB Output is correct
28 Correct 361 ms 127656 KB Output is correct
29 Correct 332 ms 125776 KB Output is correct
30 Correct 303 ms 101060 KB Output is correct
31 Correct 316 ms 100944 KB Output is correct
32 Correct 340 ms 101244 KB Output is correct
33 Correct 410 ms 100180 KB Output is correct
34 Correct 254 ms 100176 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 91188 KB Output is correct
2 Correct 130 ms 91220 KB Output is correct
3 Correct 133 ms 91080 KB Output is correct
4 Correct 129 ms 91084 KB Output is correct
5 Correct 128 ms 91204 KB Output is correct
6 Correct 129 ms 91216 KB Output is correct
7 Correct 137 ms 91040 KB Output is correct
8 Correct 135 ms 91216 KB Output is correct
9 Correct 129 ms 91220 KB Output is correct
10 Correct 135 ms 91216 KB Output is correct
11 Correct 137 ms 91216 KB Output is correct
12 Correct 140 ms 91220 KB Output is correct
13 Correct 128 ms 91048 KB Output is correct
14 Correct 128 ms 91216 KB Output is correct
15 Correct 132 ms 91028 KB Output is correct
16 Correct 133 ms 91216 KB Output is correct
17 Correct 128 ms 91116 KB Output is correct
18 Correct 127 ms 91220 KB Output is correct
19 Correct 130 ms 91216 KB Output is correct
20 Correct 134 ms 91220 KB Output is correct
21 Runtime error 195 ms 184716 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -