Submission #1152733

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1152733	2025-02-18 09:57:33	xnqs	Bridges (APIO19_bridges)	C++20	30 / 100	3107 ms	440668 KiB

bridges

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
/*
 * The main idea is to view the updates as time segments, more exactly an update has a start time and end time.
 * We will solve the queries offline, sorting them in ascending order of weight. Depending on where in the timeline
 * that query happened, we will work in one of the sqrt(N) DSUs that includes that timeline. This way, using DSU with
 * rollback, we can solve each query in O(sqrt(N)*log(N)), because there are at most sqrt(N) updates in a sqrt block.
 * Also, apparently the nodes are very small, so *maybe* we can try using uint16_t's to save some memory?
 *
 * Total time complexity: O(N*sqrt(N)*log(N))
 * Total space complexity: O(N*sqrt(N))
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <numeric>
#include <unordered_map>
#include <cstdint>
const int BLK_SIZE = 317;
class DSURollback {
private:
  struct DSUState {
    uint16_t a, old_sz, b, old_t;
    DSUState():
      a(0), old_sz(0), b(0), old_t(0) {}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27