Submission #973448

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
973448	2024-05-02 02:37:51	cot7302	Joker (BOI20_joker)	C++17	100 / 100	343 ms	16560 KiB

Joker

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
#include <bits/stdc++.h>
using namespace std;
struct disjoint_set {
    int n, odd_cir;
    vector<int> _, odd_cir_op;
    vector<tuple<int, int, int>> op;
    disjoint_set(int n) : n(n), odd_cir(0), _(2 * n + 1, -1), odd_cir_op(), op() {}
    int root(int x) { while (_[x] > 0) x = _[x]; return x; }
    void __join(int a, int b) {
        a = root(a), b = root(b);
        if (a == b) return;
        if (_[a] > _[b]) swap(a, b);
        op.emplace_back(a, b, _[b]);
        _[a] += _[b];
        _[b] = a;
    }
    void join(int a, int b) {
        __join(a, b + n);
        __join(a + n, b);
        odd_cir += odd_cir_op.emplace_back(root(a) == root(b));
    }
    void join(pair<int, int> x) {
        auto [a, b] = x;
        join(a, b);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29