Submission #648113

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
648113	2022-10-05 12:00:57	alvinpiter	Race (IOI11_race)	C++17	100 / 100	529 ms	36216 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
Subproblem:
Given a tree with N nodes, find the minimum number of edges in a path whose total length is exactly K and
it either ends at the root or pass through the root.
      root
    /  |  \
  ..  c_i  c_(i + 1)
After processing the first i children of the root, let's say we know the following:
minEdges[length] -> Minimum number of edges in a path of length "length" such that it originates from the root
and ends up at the subtree of the first i children of the root.
When processing the (i + 1)-th children, we can utilize that value. For example, we are at a node whose distance from
the root is d, then the answer we seek to minize is: depth + minEdges[K - d].
This problem can be solved in O(N) time.
To solve the full problem, we need to perform centroid decomposition. The total complexity will be O(N log(N))
*/
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXN 200000
#define MAXK 1000000
int n, k, sz[MAXN + 3];
vector<pair<int, int> > adj[MAXN + 3];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57