oj.uz

답안 #1001681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1001681 2024-06-19T06:57:16 Z Nomio 경주 (Race) (IOI11_race) C++17
31 / 100
 448 ms 184804 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;

inline void my_assert(int e)
{
  if (!e)
    abort();
}

//void read_input()
//{
//  int i;
//  my_assert(2 == scanf("%d %d", &N, &K));
//  for (i = 0; i < N - 1; i++)
//    my_assert(3 == scanf("%d %d %d", &H[i][0], &H[i][1], &L[i]));
//  my_assert(1 == scanf("%d", &solution));
//}

//int main()
//{
//  int ans;
//  read_input();
//  ans = best_path(N, K, H, L);
//  if (ans == solution)
//    printf("Correct.\n");
//  else
//    printf("Incorrect. Returned %d, Expected %d.\n", ans, solution);
//
//  return 0;
//}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 91176 KB Output is correct
2 Correct 126 ms 91216 KB Output is correct
3 Correct 122 ms 91224 KB Output is correct
4 Correct 121 ms 91220 KB Output is correct
5 Correct 126 ms 91216 KB Output is correct
6 Correct 116 ms 91132 KB Output is correct
7 Correct 128 ms 91176 KB Output is correct
8 Correct 132 ms 91248 KB Output is correct
9 Correct 128 ms 91060 KB Output is correct
10 Correct 125 ms 91204 KB Output is correct
11 Correct 124 ms 91220 KB Output is correct
12 Correct 125 ms 91024 KB Output is correct
13 Correct 143 ms 91148 KB Output is correct
14 Correct 123 ms 91204 KB Output is correct
15 Correct 124 ms 91224 KB Output is correct
16 Correct 129 ms 91220 KB Output is correct
17 Correct 130 ms 91220 KB Output is correct
18 Correct 130 ms 91216 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 91176 KB Output is correct
2 Correct 126 ms 91216 KB Output is correct
3 Correct 122 ms 91224 KB Output is correct
4 Correct 121 ms 91220 KB Output is correct
5 Correct 126 ms 91216 KB Output is correct
6 Correct 116 ms 91132 KB Output is correct
7 Correct 128 ms 91176 KB Output is correct
8 Correct 132 ms 91248 KB Output is correct
9 Correct 128 ms 91060 KB Output is correct
10 Correct 125 ms 91204 KB Output is correct
11 Correct 124 ms 91220 KB Output is correct
12 Correct 125 ms 91024 KB Output is correct
13 Correct 143 ms 91148 KB Output is correct
14 Correct 123 ms 91204 KB Output is correct
15 Correct 124 ms 91224 KB Output is correct
16 Correct 129 ms 91220 KB Output is correct
17 Correct 130 ms 91220 KB Output is correct
18 Correct 130 ms 91216 KB Output is correct
19 Correct 131 ms 91168 KB Output is correct
20 Correct 130 ms 91220 KB Output is correct
21 Runtime error 203 ms 184804 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 91176 KB Output is correct
2 Correct 126 ms 91216 KB Output is correct
3 Correct 122 ms 91224 KB Output is correct
4 Correct 121 ms 91220 KB Output is correct
5 Correct 126 ms 91216 KB Output is correct
6 Correct 116 ms 91132 KB Output is correct
7 Correct 128 ms 91176 KB Output is correct
8 Correct 132 ms 91248 KB Output is correct
9 Correct 128 ms 91060 KB Output is correct
10 Correct 125 ms 91204 KB Output is correct
11 Correct 124 ms 91220 KB Output is correct
12 Correct 125 ms 91024 KB Output is correct
13 Correct 143 ms 91148 KB Output is correct
14 Correct 123 ms 91204 KB Output is correct
15 Correct 124 ms 91224 KB Output is correct
16 Correct 129 ms 91220 KB Output is correct
17 Correct 130 ms 91220 KB Output is correct
18 Correct 130 ms 91216 KB Output is correct
19 Correct 235 ms 96080 KB Output is correct
20 Correct 233 ms 97092 KB Output is correct
21 Correct 231 ms 96712 KB Output is correct
22 Correct 263 ms 97364 KB Output is correct
23 Correct 231 ms 97616 KB Output is correct
24 Correct 223 ms 97300 KB Output is correct
25 Correct 301 ms 104020 KB Output is correct
26 Correct 270 ms 110352 KB Output is correct
27 Correct 330 ms 102724 KB Output is correct
28 Correct 371 ms 128852 KB Output is correct
29 Correct 370 ms 127144 KB Output is correct
30 Correct 317 ms 102256 KB Output is correct
31 Correct 322 ms 102312 KB Output is correct
32 Correct 353 ms 102480 KB Output is correct
33 Correct 448 ms 101452 KB Output is correct
34 Correct 271 ms 101712 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 91176 KB Output is correct
2 Correct 126 ms 91216 KB Output is correct
3 Correct 122 ms 91224 KB Output is correct
4 Correct 121 ms 91220 KB Output is correct
5 Correct 126 ms 91216 KB Output is correct
6 Correct 116 ms 91132 KB Output is correct
7 Correct 128 ms 91176 KB Output is correct
8 Correct 132 ms 91248 KB Output is correct
9 Correct 128 ms 91060 KB Output is correct
10 Correct 125 ms 91204 KB Output is correct
11 Correct 124 ms 91220 KB Output is correct
12 Correct 125 ms 91024 KB Output is correct
13 Correct 143 ms 91148 KB Output is correct
14 Correct 123 ms 91204 KB Output is correct
15 Correct 124 ms 91224 KB Output is correct
16 Correct 129 ms 91220 KB Output is correct
17 Correct 130 ms 91220 KB Output is correct
18 Correct 130 ms 91216 KB Output is correct
19 Correct 131 ms 91168 KB Output is correct
20 Correct 130 ms 91220 KB Output is correct
21 Runtime error 203 ms 184804 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -