oj.uz

답안 #598370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598370 2022-07-18T07:45:36 Z ono_de206 경주 (Race) (IOI11_race) C++14
100 / 100
 572 ms 41656 KB 
#include "race.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

#define MAXN 200050
#define MAXK 1000050

#define F first
#define S second

int N, K, global_answer; // Input and result variables
int split_node, current_max; // Variables to calculate centroid
int book_keeping; // Book keeping helper

int H[MAXN][2]; // Input variables
int L[MAXN];

int processed[MAXN]; // Markers to help main recursion
int size[MAXN]; // Size of subtrees in rooted tree
int achievable[MAXK]; // Helper arrays for minimum paths crossing v
int minimum_paths[MAXK];

vector<pii> neighbors[MAXN]; // The actual tree

///////////////////////////////////////////////
//
// Goal: Calculate the size of each subtree
//
///////////////////////////////////////////////
void calc_size(int current, int parent)
{
  size[current] = 0;

  // Recurse on unprocessed nodes and update size
  int i;
  for (i = 0; i < (int)neighbors[current].size(); i++)
    if (!processed[neighbors[current][i].F] && neighbors[current][i].F != parent)
    {
      calc_size(neighbors[current][i].F, current);
      size[current] += 1 + size[neighbors[current][i].F];
    }
}

///////////////////////////////////////////////
//
// Goal: Calculate the centroid
//
///////////////////////////////////////////////
void select_split_node(int current, int parent, int total)
{
  int node_max = (total - size[current] - 1);

  // Recurse on unprocessed nodes updating the maximum subtree on node_max
  int i;
  for (i = 0; i < (int)neighbors[current].size(); i++)
    if (!processed[neighbors[current][i].F] && neighbors[current][i].F != parent)
    {
      select_split_node(neighbors[current][i].F, current, total);
      node_max = max(node_max, 1 + size[neighbors[current][i].F]);
    }

  if (node_max < current_max)
  {
    split_node = current;
    current_max = node_max;
  }
}

///////////////////////////////////////////////
//
// Goal: DFS from the centroid to calculate all paths
//
///////////////////////////////////////////////
void dfs_from_node(int current, int parent, int current_cost, int current_length, int fill)
{
  if (current_cost > K)
    return;

  if (!fill) // If we are calculating the paths
  {
    if (achievable[K - current_cost] == book_keeping)
      if (current_length + minimum_paths[K - current_cost] < global_answer || global_answer == -1)
        global_answer = current_length + minimum_paths[K - current_cost];

    if (current_cost == K)
      if (current_length < global_answer || global_answer == -1)
        global_answer = current_length;
  }
  else // If we are filling the helper array
  {
    if (achievable[current_cost] < book_keeping)
    {
      achievable[current_cost] = book_keeping;
      minimum_paths[current_cost] = current_length;
    }
    else if (current_length < minimum_paths[current_cost])
    {
      achievable[current_cost] = book_keeping;
      minimum_paths[current_cost] = current_length;
    }
  }

  // Recurse on unprocessed nodes
  int i;
  for (i = 0; i < (int)neighbors[current].size(); i++)
    if (!processed[neighbors[current][i].F] && neighbors[current][i].F != parent)
      dfs_from_node(neighbors[current][i].F, current, current_cost + neighbors[current][i].S, current_length + 1, fill);
}

///////////////////////////////////////////////
//
// Goal: Calculate best for subtree
//
///////////////////////////////////////////////
void process(int current)
{
  // Fill the size array
  calc_size(current, -1);

  // Base case
  if (size[current] <= 1)
    return;

  // Calculate the centroid and put it in split_node
  split_node = -1;
  current_max = size[current] + 3;
  select_split_node(current, -1, size[current] + 1);

  // Double dfs to calculate minimums and fill helper array
  book_keeping++;
  int i;
  for (i = 0; i < (int)neighbors[split_node].size(); i++)
    if (!processed[neighbors[split_node][i].F])
    {
      dfs_from_node(neighbors[split_node][i].F, split_node, neighbors[split_node][i].S, 1, 0);
      dfs_from_node(neighbors[split_node][i].F, split_node, neighbors[split_node][i].S, 1, 1);
    }


  int local_split_node = split_node; // Since split_node is global
  processed[split_node] = 1; // Mark as processed to cap recursion

  // Call main method on each subtree from centroid
  for (i = 0; i < (int)neighbors[local_split_node].size(); i++)
    if (!processed[neighbors[local_split_node][i].F])
      process(neighbors[local_split_node][i].F);
}

///////////////////////////////////////////////
//
// Goal: Answer the task
//
///////////////////////////////////////////////
int best_path(int _N, int _K, int H[][2], int L[])
{
  // Reset arrays and variables
  memset(processed, 0, sizeof processed);
  memset(achievable, 0, sizeof achievable);
  memset(minimum_paths, 0, sizeof minimum_paths);
  N = _N;
  K = _K;
  book_keeping = 0;

  // Build tree
  int i;
  for (i = 0; i < N - 1; i++)
  {
    neighbors[H[i][0]].push_back(pii(H[i][1], L[i]));
    neighbors[H[i][1]].push_back(pii(H[i][0], L[i]));
  }

  global_answer = -1;

  // Call main method for whole tree
  process(0);

  return global_answer;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 13524 KB Output is correct
2 Correct 7 ms 13524 KB Output is correct
3 Correct 6 ms 13632 KB Output is correct
4 Correct 6 ms 13524 KB Output is correct
5 Correct 6 ms 13524 KB Output is correct
6 Correct 6 ms 13552 KB Output is correct
7 Correct 8 ms 13520 KB Output is correct
8 Correct 6 ms 13524 KB Output is correct
9 Correct 9 ms 13528 KB Output is correct
10 Correct 7 ms 13524 KB Output is correct
11 Correct 7 ms 13636 KB Output is correct
12 Correct 6 ms 13524 KB Output is correct
13 Correct 6 ms 13556 KB Output is correct
14 Correct 7 ms 13524 KB Output is correct
15 Correct 6 ms 13600 KB Output is correct
16 Correct 6 ms 13524 KB Output is correct
17 Correct 6 ms 13524 KB Output is correct
18 Correct 6 ms 13524 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 13524 KB Output is correct
2 Correct 7 ms 13524 KB Output is correct
3 Correct 6 ms 13632 KB Output is correct
4 Correct 6 ms 13524 KB Output is correct
5 Correct 6 ms 13524 KB Output is correct
6 Correct 6 ms 13552 KB Output is correct
7 Correct 8 ms 13520 KB Output is correct
8 Correct 6 ms 13524 KB Output is correct
9 Correct 9 ms 13528 KB Output is correct
10 Correct 7 ms 13524 KB Output is correct
11 Correct 7 ms 13636 KB Output is correct
12 Correct 6 ms 13524 KB Output is correct
13 Correct 6 ms 13556 KB Output is correct
14 Correct 7 ms 13524 KB Output is correct
15 Correct 6 ms 13600 KB Output is correct
16 Correct 6 ms 13524 KB Output is correct
17 Correct 6 ms 13524 KB Output is correct
18 Correct 6 ms 13524 KB Output is correct
19 Correct 7 ms 13524 KB Output is correct
20 Correct 7 ms 13536 KB Output is correct
21 Correct 7 ms 13652 KB Output is correct
22 Correct 7 ms 13624 KB Output is correct
23 Correct 7 ms 13672 KB Output is correct
24 Correct 7 ms 13652 KB Output is correct
25 Correct 7 ms 13672 KB Output is correct
26 Correct 7 ms 13652 KB Output is correct
27 Correct 7 ms 13680 KB Output is correct
28 Correct 7 ms 13652 KB Output is correct
29 Correct 8 ms 13652 KB Output is correct
30 Correct 7 ms 13652 KB Output is correct
31 Correct 7 ms 13596 KB Output is correct
32 Correct 7 ms 13652 KB Output is correct
33 Correct 7 ms 13680 KB Output is correct
34 Correct 7 ms 13652 KB Output is correct
35 Correct 7 ms 13652 KB Output is correct
36 Correct 8 ms 13608 KB Output is correct
37 Correct 7 ms 13652 KB Output is correct
38 Correct 7 ms 13652 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 13524 KB Output is correct
2 Correct 7 ms 13524 KB Output is correct
3 Correct 6 ms 13632 KB Output is correct
4 Correct 6 ms 13524 KB Output is correct
5 Correct 6 ms 13524 KB Output is correct
6 Correct 6 ms 13552 KB Output is correct
7 Correct 8 ms 13520 KB Output is correct
8 Correct 6 ms 13524 KB Output is correct
9 Correct 9 ms 13528 KB Output is correct
10 Correct 7 ms 13524 KB Output is correct
11 Correct 7 ms 13636 KB Output is correct
12 Correct 6 ms 13524 KB Output is correct
13 Correct 6 ms 13556 KB Output is correct
14 Correct 7 ms 13524 KB Output is correct
15 Correct 6 ms 13600 KB Output is correct
16 Correct 6 ms 13524 KB Output is correct
17 Correct 6 ms 13524 KB Output is correct
18 Correct 6 ms 13524 KB Output is correct
19 Correct 191 ms 18808 KB Output is correct
20 Correct 150 ms 20084 KB Output is correct
21 Correct 150 ms 20100 KB Output is correct
22 Correct 165 ms 20288 KB Output is correct
23 Correct 98 ms 20460 KB Output is correct
24 Correct 62 ms 20400 KB Output is correct
25 Correct 145 ms 23764 KB Output is correct
26 Correct 100 ms 27396 KB Output is correct
27 Correct 178 ms 27236 KB Output is correct
28 Correct 380 ms 41656 KB Output is correct
29 Correct 341 ms 40464 KB Output is correct
30 Correct 183 ms 27104 KB Output is correct
31 Correct 179 ms 27200 KB Output is correct
32 Correct 227 ms 27356 KB Output is correct
33 Correct 252 ms 26056 KB Output is correct
34 Correct 253 ms 26740 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 13524 KB Output is correct
2 Correct 7 ms 13524 KB Output is correct
3 Correct 6 ms 13632 KB Output is correct
4 Correct 6 ms 13524 KB Output is correct
5 Correct 6 ms 13524 KB Output is correct
6 Correct 6 ms 13552 KB Output is correct
7 Correct 8 ms 13520 KB Output is correct
8 Correct 6 ms 13524 KB Output is correct
9 Correct 9 ms 13528 KB Output is correct
10 Correct 7 ms 13524 KB Output is correct
11 Correct 7 ms 13636 KB Output is correct
12 Correct 6 ms 13524 KB Output is correct
13 Correct 6 ms 13556 KB Output is correct
14 Correct 7 ms 13524 KB Output is correct
15 Correct 6 ms 13600 KB Output is correct
16 Correct 6 ms 13524 KB Output is correct
17 Correct 6 ms 13524 KB Output is correct
18 Correct 6 ms 13524 KB Output is correct
19 Correct 7 ms 13524 KB Output is correct
20 Correct 7 ms 13536 KB Output is correct
21 Correct 7 ms 13652 KB Output is correct
22 Correct 7 ms 13624 KB Output is correct
23 Correct 7 ms 13672 KB Output is correct
24 Correct 7 ms 13652 KB Output is correct
25 Correct 7 ms 13672 KB Output is correct
26 Correct 7 ms 13652 KB Output is correct
27 Correct 7 ms 13680 KB Output is correct
28 Correct 7 ms 13652 KB Output is correct
29 Correct 8 ms 13652 KB Output is correct
30 Correct 7 ms 13652 KB Output is correct
31 Correct 7 ms 13596 KB Output is correct
32 Correct 7 ms 13652 KB Output is correct
33 Correct 7 ms 13680 KB Output is correct
34 Correct 7 ms 13652 KB Output is correct
35 Correct 7 ms 13652 KB Output is correct
36 Correct 8 ms 13608 KB Output is correct
37 Correct 7 ms 13652 KB Output is correct
38 Correct 7 ms 13652 KB Output is correct
39 Correct 191 ms 18808 KB Output is correct
40 Correct 150 ms 20084 KB Output is correct
41 Correct 150 ms 20100 KB Output is correct
42 Correct 165 ms 20288 KB Output is correct
43 Correct 98 ms 20460 KB Output is correct
44 Correct 62 ms 20400 KB Output is correct
45 Correct 145 ms 23764 KB Output is correct
46 Correct 100 ms 27396 KB Output is correct
47 Correct 178 ms 27236 KB Output is correct
48 Correct 380 ms 41656 KB Output is correct
49 Correct 341 ms 40464 KB Output is correct
50 Correct 183 ms 27104 KB Output is correct
51 Correct 179 ms 27200 KB Output is correct
52 Correct 227 ms 27356 KB Output is correct
53 Correct 252 ms 26056 KB Output is correct
54 Correct 253 ms 26740 KB Output is correct
55 Correct 15 ms 14256 KB Output is correct
56 Correct 15 ms 14164 KB Output is correct
57 Correct 89 ms 20520 KB Output is correct
58 Correct 35 ms 20072 KB Output is correct
59 Correct 114 ms 27456 KB Output is correct
60 Correct 480 ms 40784 KB Output is correct
61 Correct 231 ms 27296 KB Output is correct
62 Correct 195 ms 27264 KB Output is correct
63 Correct 298 ms 27408 KB Output is correct
64 Correct 572 ms 27520 KB Output is correct
65 Correct 279 ms 27804 KB Output is correct
66 Correct 422 ms 38056 KB Output is correct
67 Correct 107 ms 27816 KB Output is correct
68 Correct 270 ms 27980 KB Output is correct
69 Correct 266 ms 28108 KB Output is correct
70 Correct 250 ms 27484 KB Output is correct