oj.uz

Submission #865949

# Submission time Handle Problem Language Result Execution time Memory
865949 2023-10-25T05:24:01 Z tamir1 Race (IOI11_race) C++14
100 / 100
 321 ms 46412 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;
}

///////////////////////////////////////////////
//
// Goal: Read the input
//
///////////////////////////////////////////////

///////////////////////////////////////////////
//
// Goal: Main
//
///////////////////////////////////////////////

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18880 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 3 ms 18776 KB Output is correct
10 Correct 3 ms 18776 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Correct 3 ms 18780 KB Output is correct
13 Correct 3 ms 18780 KB Output is correct
14 Correct 3 ms 18780 KB Output is correct
15 Correct 3 ms 18780 KB Output is correct
16 Correct 3 ms 18780 KB Output is correct
17 Correct 3 ms 18780 KB Output is correct
18 Correct 3 ms 18780 KB Output is correct
19 Correct 99 ms 24144 KB Output is correct
20 Correct 110 ms 24268 KB Output is correct
21 Correct 101 ms 24156 KB Output is correct
22 Correct 94 ms 24148 KB Output is correct
23 Correct 63 ms 24400 KB Output is correct
24 Correct 43 ms 24408 KB Output is correct
25 Correct 104 ms 27864 KB Output is correct
26 Correct 81 ms 31312 KB Output is correct
27 Correct 135 ms 32000 KB Output is correct
28 Correct 197 ms 46412 KB Output is correct
29 Correct 186 ms 45500 KB Output is correct
30 Correct 108 ms 32084 KB Output is correct
31 Correct 110 ms 32080 KB Output is correct
32 Correct 131 ms 32068 KB Output is correct
33 Correct 164 ms 31056 KB Output is correct
34 Correct 134 ms 31932 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18880 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 3 ms 18776 KB Output is correct
10 Correct 3 ms 18776 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Correct 3 ms 18780 KB Output is correct
13 Correct 3 ms 18780 KB Output is correct
14 Correct 3 ms 18780 KB Output is correct
15 Correct 3 ms 18780 KB Output is correct
16 Correct 3 ms 18780 KB Output is correct
17 Correct 3 ms 18780 KB Output is correct
18 Correct 3 ms 18780 KB Output is correct
19 Correct 3 ms 18776 KB Output is correct
20 Correct 3 ms 18780 KB Output is correct
21 Correct 3 ms 18780 KB Output is correct
22 Correct 3 ms 18780 KB Output is correct
23 Correct 3 ms 18776 KB Output is correct
24 Correct 3 ms 18780 KB Output is correct
25 Correct 3 ms 18780 KB Output is correct
26 Correct 3 ms 18780 KB Output is correct
27 Correct 3 ms 18780 KB Output is correct
28 Correct 3 ms 18888 KB Output is correct
29 Correct 4 ms 18780 KB Output is correct
30 Correct 3 ms 18780 KB Output is correct
31 Correct 4 ms 18776 KB Output is correct
32 Correct 3 ms 18780 KB Output is correct
33 Correct 3 ms 18780 KB Output is correct
34 Correct 3 ms 18780 KB Output is correct
35 Correct 3 ms 18780 KB Output is correct
36 Correct 3 ms 18912 KB Output is correct
37 Correct 3 ms 18776 KB Output is correct
38 Correct 3 ms 18780 KB Output is correct
39 Correct 99 ms 24144 KB Output is correct
40 Correct 110 ms 24268 KB Output is correct
41 Correct 101 ms 24156 KB Output is correct
42 Correct 94 ms 24148 KB Output is correct
43 Correct 63 ms 24400 KB Output is correct
44 Correct 43 ms 24408 KB Output is correct
45 Correct 104 ms 27864 KB Output is correct
46 Correct 81 ms 31312 KB Output is correct
47 Correct 135 ms 32000 KB Output is correct
48 Correct 197 ms 46412 KB Output is correct
49 Correct 186 ms 45500 KB Output is correct
50 Correct 108 ms 32084 KB Output is correct
51 Correct 110 ms 32080 KB Output is correct
52 Correct 131 ms 32068 KB Output is correct
53 Correct 164 ms 31056 KB Output is correct
54 Correct 134 ms 31932 KB Output is correct
55 Correct 9 ms 19396 KB Output is correct
56 Correct 11 ms 19336 KB Output is correct
57 Correct 68 ms 24404 KB Output is correct
58 Correct 26 ms 24200 KB Output is correct
59 Correct 86 ms 31560 KB Output is correct
60 Correct 321 ms 45652 KB Output is correct
61 Correct 124 ms 32264 KB Output is correct
62 Correct 126 ms 32228 KB Output is correct
63 Correct 167 ms 32084 KB Output is correct
64 Correct 310 ms 32492 KB Output is correct
65 Correct 150 ms 33060 KB Output is correct
66 Correct 285 ms 43068 KB Output is correct
67 Correct 64 ms 32908 KB Output is correct
68 Correct 183 ms 33228 KB Output is correct
69 Correct 184 ms 33104 KB Output is correct
70 Correct 173 ms 32592 KB Output is correct