Submission #1123205

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1123205	2024-12-02 12:42:23	Thunnus	Synchronization (JOI13_synchronization)	C++20	100 / 100	208 ms	21512 KiB

synchronization

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
/*
JOI 2013 Synchronisation
- In this problem, we essentially want to synchronise data between connected components
  in a forest. We need to support 4 types of queries:
    - Set all nodes in a connected component to have value x
    - Find the value in some node
    - Split a connected component
    - Join 2 connected components
- 1) How do we sync data without actually storing the computers that have synced?
    - Let u and v be connected, where u is the parent of v
    - For each node v, store a value info[v] which denotes the amount of info in it
    - Let last_sync[v] be the amount of data that was common between u and v
      the last time they synced
    - Clearly, the new amount of data (newval) will be info[u] + info[v] - last_sync[v]
      if we connect u and v
    - Simply set info[u] = info[v] = last_sync[v] = newval
- 2) How can we represent connected components?
    - Root the tree arbitrarily
    - Each connected component must have a single lowest ancestor
    - We can do all operations for that connected component on that ancestor
    - We can find it in O(log^2 N) with DFS, binary lifting, and a Fenwick tree
        - First find the dfs order of the nodes (i.e. find tin and tout)
        - Update a node in the Fenwick tree to be +1 if it has an active edge to its parent
        - Notice that we can do path queries if we update tin[node] -> +1 and tout[node] -> -1
        - Let query(x) be the sum from the Fenwick tree from 1 to x
        - u is an ancestor of v iff query(u) == query(v)
        - Thus we can use binary lifting to find the lowest ancestor of a component
- 3) How can we process a split/union?
    - Let u and v be the edge concerned, where u is the parent of v
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40