Submission #602521

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
602521	2022-07-23 07:30:13	jophyyjh	Job Scheduling (IOI19_job)	C++14	100 / 100	243 ms	18748 KiB

job

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
/**
 * What an interesting pratice contest problem! I could only solve the first 3
 * subtasks. (they're really trivial...) After that I searched online for an answer.
 * 
 * The idea is like "Chain Reactions" (Google Code Jam 2022 Qual.). Since a node can
 * only be chosen when its parent has been, we try to carefully merge leaf nodes into
 * their parent through a greedy approach. Previously, I tried too hard on
 * identifying the first / last selected node, which can be quite difficult when our
 * search base is the whole tree.
 * 
 * Each time, we try to find a node v with the smallest d[]/u[]. (This node need not
 * be a leaf.) We try to merge v into its parent p, i.e. u[p] += u[v], d[p] += d[v],
 * adjust the cost and let children of v have p as their direct parent. Why is
 * this greedy correct?
 * Although it could be difficult to determine which leaf is the last / which node
 * is the first, if v has the smallest d[]/u[], there exists a optimal schedule in
 * which v is built immediately after p is built. Simple argument of "exchange" can
 * prove this. In such case, we can just consider the time diff. (and add the
 * additional cost). Note that all children of v now have p as their direct parent
 * because once v and p are built, all children of v can start.
 * Learnt lots of stuff from this problem!
 * 
 * PS1  The solution above is inspired by Tutis (from Codeforces) in
 *      https://codeforces.com/blog/entry/68632.
 * PS2  When we apply our greedy strategy, the tree may be splited, forming a
 *      forest. We can add a pseudo root (the original -1 in parents[]) to simplify
 *      our code.
 * 
 * Time Complexity: O(n * log(n))
 * Implementation 2     (full solution, inspired by Tutis from Codeforces)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 37 / 37