oj.uz

Submission #909389

# Submission time Handle Problem Language Result Execution time Memory
909389 2024-01-17T07:43:58 Z tnun Race (IOI11_race) C++14
100 / 100
 424 ms 46484 KB 
///////////////////////////////////////////////
//
//  _____    ____    _____      ___     ___    __   __ 
// |_   _|  / __ \  |_   _|    |__ \   / _ \  /_ | /_ |
//   | |   | |  | |   | |         ) | | | | |  | |  | |
//   | |   | |  | |   | |        / /  | | | |  | |  | |
//  _| |_  | |__| |  _| |_      / /_  | |_| |  | |  | |
// |_____|  \____/  |_____|    |____|  \___/   |_|  |_|
//
//
// Year: IOI'2011
// Problem: Race, Day 1
// Solution: 100 Points, O(NlogN)
// Author: Pedro Paredes
//
///////////////////////////////////////////////

#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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 5 ms 18780 KB Output is correct
3 Correct 5 ms 18776 KB Output is correct
4 Correct 5 ms 18780 KB Output is correct
5 Correct 4 ms 18868 KB Output is correct
6 Correct 5 ms 18780 KB Output is correct
7 Correct 5 ms 18780 KB Output is correct
8 Correct 4 ms 18776 KB Output is correct
9 Correct 4 ms 18780 KB Output is correct
10 Correct 4 ms 18888 KB Output is correct
11 Correct 4 ms 19032 KB Output is correct
12 Correct 4 ms 18780 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18776 KB Output is correct
15 Correct 4 ms 19136 KB Output is correct
16 Correct 5 ms 18876 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 5 ms 18780 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 5 ms 18780 KB Output is correct
3 Correct 5 ms 18776 KB Output is correct
4 Correct 5 ms 18780 KB Output is correct
5 Correct 4 ms 18868 KB Output is correct
6 Correct 5 ms 18780 KB Output is correct
7 Correct 5 ms 18780 KB Output is correct
8 Correct 4 ms 18776 KB Output is correct
9 Correct 4 ms 18780 KB Output is correct
10 Correct 4 ms 18888 KB Output is correct
11 Correct 4 ms 19032 KB Output is correct
12 Correct 4 ms 18780 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18776 KB Output is correct
15 Correct 4 ms 19136 KB Output is correct
16 Correct 5 ms 18876 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 5 ms 18780 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 5 ms 18776 KB Output is correct
21 Correct 5 ms 18780 KB Output is correct
22 Correct 4 ms 18912 KB Output is correct
23 Correct 4 ms 18780 KB Output is correct
24 Correct 4 ms 18780 KB Output is correct
25 Correct 4 ms 18780 KB Output is correct
26 Correct 5 ms 18780 KB Output is correct
27 Correct 5 ms 18884 KB Output is correct
28 Correct 4 ms 18780 KB Output is correct
29 Correct 5 ms 18904 KB Output is correct
30 Correct 5 ms 18780 KB Output is correct
31 Correct 5 ms 18780 KB Output is correct
32 Correct 5 ms 18780 KB Output is correct
33 Correct 5 ms 18780 KB Output is correct
34 Correct 5 ms 18792 KB Output is correct
35 Correct 5 ms 18780 KB Output is correct
36 Correct 5 ms 18776 KB Output is correct
37 Correct 5 ms 18776 KB Output is correct
38 Correct 5 ms 18780 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 5 ms 18780 KB Output is correct
3 Correct 5 ms 18776 KB Output is correct
4 Correct 5 ms 18780 KB Output is correct
5 Correct 4 ms 18868 KB Output is correct
6 Correct 5 ms 18780 KB Output is correct
7 Correct 5 ms 18780 KB Output is correct
8 Correct 4 ms 18776 KB Output is correct
9 Correct 4 ms 18780 KB Output is correct
10 Correct 4 ms 18888 KB Output is correct
11 Correct 4 ms 19032 KB Output is correct
12 Correct 4 ms 18780 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18776 KB Output is correct
15 Correct 4 ms 19136 KB Output is correct
16 Correct 5 ms 18876 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 5 ms 18780 KB Output is correct
19 Correct 103 ms 24272 KB Output is correct
20 Correct 104 ms 24148 KB Output is correct
21 Correct 105 ms 24148 KB Output is correct
22 Correct 101 ms 24384 KB Output is correct
23 Correct 76 ms 24400 KB Output is correct
24 Correct 50 ms 24400 KB Output is correct
25 Correct 105 ms 27668 KB Output is correct
26 Correct 97 ms 31324 KB Output is correct
27 Correct 146 ms 32096 KB Output is correct
28 Correct 268 ms 46484 KB Output is correct
29 Correct 230 ms 45640 KB Output is correct
30 Correct 134 ms 32080 KB Output is correct
31 Correct 118 ms 32164 KB Output is correct
32 Correct 132 ms 32080 KB Output is correct
33 Correct 179 ms 31060 KB Output is correct
34 Correct 146 ms 31820 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 5 ms 18780 KB Output is correct
3 Correct 5 ms 18776 KB Output is correct
4 Correct 5 ms 18780 KB Output is correct
5 Correct 4 ms 18868 KB Output is correct
6 Correct 5 ms 18780 KB Output is correct
7 Correct 5 ms 18780 KB Output is correct
8 Correct 4 ms 18776 KB Output is correct
9 Correct 4 ms 18780 KB Output is correct
10 Correct 4 ms 18888 KB Output is correct
11 Correct 4 ms 19032 KB Output is correct
12 Correct 4 ms 18780 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18776 KB Output is correct
15 Correct 4 ms 19136 KB Output is correct
16 Correct 5 ms 18876 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 5 ms 18780 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 5 ms 18776 KB Output is correct
21 Correct 5 ms 18780 KB Output is correct
22 Correct 4 ms 18912 KB Output is correct
23 Correct 4 ms 18780 KB Output is correct
24 Correct 4 ms 18780 KB Output is correct
25 Correct 4 ms 18780 KB Output is correct
26 Correct 5 ms 18780 KB Output is correct
27 Correct 5 ms 18884 KB Output is correct
28 Correct 4 ms 18780 KB Output is correct
29 Correct 5 ms 18904 KB Output is correct
30 Correct 5 ms 18780 KB Output is correct
31 Correct 5 ms 18780 KB Output is correct
32 Correct 5 ms 18780 KB Output is correct
33 Correct 5 ms 18780 KB Output is correct
34 Correct 5 ms 18792 KB Output is correct
35 Correct 5 ms 18780 KB Output is correct
36 Correct 5 ms 18776 KB Output is correct
37 Correct 5 ms 18776 KB Output is correct
38 Correct 5 ms 18780 KB Output is correct
39 Correct 103 ms 24272 KB Output is correct
40 Correct 104 ms 24148 KB Output is correct
41 Correct 105 ms 24148 KB Output is correct
42 Correct 101 ms 24384 KB Output is correct
43 Correct 76 ms 24400 KB Output is correct
44 Correct 50 ms 24400 KB Output is correct
45 Correct 105 ms 27668 KB Output is correct
46 Correct 97 ms 31324 KB Output is correct
47 Correct 146 ms 32096 KB Output is correct
48 Correct 268 ms 46484 KB Output is correct
49 Correct 230 ms 45640 KB Output is correct
50 Correct 134 ms 32080 KB Output is correct
51 Correct 118 ms 32164 KB Output is correct
52 Correct 132 ms 32080 KB Output is correct
53 Correct 179 ms 31060 KB Output is correct
54 Correct 146 ms 31820 KB Output is correct
55 Correct 11 ms 19288 KB Output is correct
56 Correct 11 ms 19292 KB Output is correct
57 Correct 80 ms 24400 KB Output is correct
58 Correct 28 ms 24252 KB Output is correct
59 Correct 86 ms 31568 KB Output is correct
60 Correct 401 ms 45652 KB Output is correct
61 Correct 162 ms 32296 KB Output is correct
62 Correct 156 ms 32260 KB Output is correct
63 Correct 245 ms 32080 KB Output is correct
64 Correct 424 ms 32492 KB Output is correct
65 Correct 168 ms 32984 KB Output is correct
66 Correct 341 ms 43068 KB Output is correct
67 Correct 69 ms 32712 KB Output is correct
68 Correct 213 ms 32848 KB Output is correct
69 Correct 185 ms 33452 KB Output is correct
70 Correct 166 ms 32612 KB Output is correct