A - Disjoint Set Union
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7
8class UnionTree {
9private:
10 vector<int> par, sz;
11public:
12 UnionTree(int n) {
13 par.resize(n);
14 for (int i = 0; i < n; i++) {
15 par[i] = i;
16 }
17 sz.resize(n, 1);
18 }
19 int findPar(int x) {
20 return par[x] = (x == par[x] ? x : findPar(par[x]));
21 }
22 bool isSame(int a, int b) {
23 return findPar(a) == findPar(b);
24 }
25 void uni(int a, int b) {
26 if (isSame(a, b)) {
27 return;
28 }
29 a = par[a];
30 b = par[b];
31 if (sz[a] < sz[b]) {
32 swap(a, b);
33 }
34 sz[a] += sz[b];
35 par[b] = a;
36 }
37};
38
39int main() {
40 ios::sync_with_stdio(0), cin.tie(0);
41 int n, q;
42 cin >> n >> q;
43 UnionTree UT(n);
44 for (int i = 0; i < q; i++) {
45 int t, u, v;
46 cin >> t >> u >> v;
47 if (t == 0) {
48 UT.uni(u, v);
49 } else {
50 cout << UT.isSame(u, v) << "\n";
51 }
52 }
53 return 0;
54}
B - Fenwick Tree
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5typedef pair<int, int> pii;
6#define pb push_back
7#define maxn 500005
8
9class RangeUpdateBIT {
10 private:
11 ll d[maxn], dd[maxn];
12 ll sum(int i) {
13 ll s = 0, ss = 0;
14 int c = i + 1;
15 while (i > 0) s += d[i], ss += dd[i], i -= i & -i;
16 return c * s - ss;
17 }
18 void add(int i, ll v) {
19 int c = i;
20 while (i < maxn)
21 d[i] += v, dd[i] += c * v, i += i & -i;
22 }
23 public:
24 RangeUpdateBIT() {
25 memset(d, 0, sizeof(d));
26 memset(dd, 0, sizeof(dd));
27 }
28 ll sum(int l, int r) { return sum(r) - sum(l - 1); }
29 void add(int l, int r, ll v) {
30 add(l, v), add(r + 1, -v);
31 }
32};
33
34int main() {
35 ios::sync_with_stdio(0), cin.tie(0);
36 int n, q;
37 cin >> n >> q;
38 RangeUpdateBIT BIT;
39 for (int i = 0; i < n; i++) {
40 int a;
41 cin >> a;
42 BIT.add(i + 1, i + 1, a);
43 }
44 for (int i = 0; i < q; i++) {
45 int t;
46 cin >> t;;
47 if (t == 0) {
48 int p, x;
49 cin >> p >> x;
50 BIT.add(p + 1, p + 1, x);
51 } else {
52 int l, r;
53 cin >> l >> r;
54 cout << BIT.sum(l + 1, r) << "\n";
55 }
56 }
57 return 0;
58}
D - Maxflow
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3#include <atcoder/all>
4using namespace std;
5using namespace atcoder;
6typedef long long ll;
7typedef pair<int, int> pii;
8#define pb push_back
9
10int main() {
11 ios::sync_with_stdio(0), cin.tie(0);
12 int n, m;
13 cin >> n >> m;
14 vector<string> input(n);
15 for (int i = 0; i < n; i++) {
16 cin >> input[i];
17 }
18 mf_graph<int> G(n * m + 2);
19 int src = n * m;
20 int dst = src + 1;
21 const int dx[4] = {1, -1, 0, 0};
22 const int dy[4] = {0, 0, 1, -1};
23 for (int i = 0; i < n; i++) {
24 for (int j = 0; j < m; j++) {
25 if (input[i][j] == '#') {
26 continue;
27 }
28 int id = i * m + j;
29 if ((i + j) & 1) { // white
30 G.add_edge(id, dst, 1);
31 } else { // black
32 G.add_edge(src, id, 1);
33 for (int di = 0; di < 4; di++) {
34 int ii = i + dx[di];
35 int jj = j + dy[di];
36 if (ii < 0 || ii >= n ||
37 jj < 0 || jj >= m ||
38 input[ii][jj] == '#') {
39 continue;
40 }
41 int id2 = ii * m + jj;
42 G.add_edge(id, id2, 1);
43 }
44 }
45 }
46 }
47 auto output = input;
48 int max_flow = G.flow(src, dst);
49 for (auto e : G.edges()) {
50 if (e.from == src || e.to == dst || e.flow == 0) {
51 continue;
52 }
53 int x1 = e.from / m;
54 int x2 = e.to / m;
55 int y1 = e.from % m;
56 int y2 = e.to % m;
57 if (x1 == x2) {
58 if (y1 > y2) {
59 swap(y1, y2);
60 }
61 output[x1][y1] = '>';
62 output[x2][y2] = '<';
63 } else if (y1 == y2) {
64 if (x1 > x2) {
65 swap(x1, x2);
66 }
67 output[x1][y1] = 'v';
68 output[x2][y2] = '^';
69 }
70 }
71 cout << max_flow << "\n";
72 for (int i = 0; i < n; i++) {
73 cout << output[i] << '\n';
74 }
75 return 0;
76}
E - MinCostFlow
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3#include <atcoder/all>
4using namespace std;
5using namespace atcoder;
6typedef long long ll;
7typedef pair<int, int> pii;
8#define pb push_back
9
10int main() {
11 ios::sync_with_stdio(0), cin.tie(0);
12 int n, k;
13 cin >> n >> k;
14 vector<vector<int>> input(n, vector<int>(n));
15 for (int i = 0; i < n; i++) {
16 for (int j = 0; j < n; j++) {
17 cin >> input[i][j];
18 }
19 }
20 const int max_cap = 1000000009;
21 const int inf = 1000000009;
22 int src = 2 * n;
23 int snk = src + 1;
24 mcf_graph<int, ll> G(2 * n + 2);
25 for (int i = 0; i < n; i++) {
26 for (int j = 0; j < n; j++) {
27 G.add_edge(i, j + n, 1, max_cap - input[i][j]);
28 }
29 G.add_edge(src, i, k, 0);
30 G.add_edge(i + n, snk, k, 0);
31 }
32 G.add_edge(src, snk, inf, max_cap);
33 G.flow(src, snk, n * k);
34 vector<vector<char>> output(n, vector<char>(n, '.'));
35 ll ans = 0;
36 for (auto e : G.edges()) {
37 if (e.from == src || e.to == snk || e.flow == 0) {
38 continue;
39 }
40 int i = e.from;
41 int j = e.to - n;
42 output[i][j] = 'X';
43 ans += max_cap - e.cost;
44 }
45 cout << ans << '\n';
46 for (int i = 0; i < n; i++) {
47 for (int j = 0; j < n; j++) {
48 cout << output[i][j];
49 }
50 cout << '\n';
51 }
52 return 0;
53}
F - Convolution
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3#include <atcoder/all>
4using namespace std;
5using namespace atcoder;
6typedef long long ll;
7typedef pair<int, int> pii;
8#define pb push_back
9
10int main() {
11 ios::sync_with_stdio(0), cin.tie(0);
12 int N, M;
13 cin >> N >> M;
14 vector<int> a(N), b(M);
15 for (int i = 0; i < N; i++) {
16 cin >> a[i];
17 }
18 for (int i = 0; i < M; i++) {
19 cin >> b[i];
20 }
21 auto c = convolution(a, b);
22 for (int i = 0; i < N + M - 1; i++) {
23 cout << c[i] << " \n"[i == N + M - 2];
24 }
25 return 0;
26}
G - SCC
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3#include <atcoder/all>
4using namespace std;
5using namespace atcoder;
6typedef long long ll;
7typedef pair<int, int> pii;
8#define pb push_back
9
10int main() {
11 ios::sync_with_stdio(0), cin.tie(0);
12 int n, m;
13 cin >> n >> m;
14 scc_graph G(n);
15 for (int i = 0; i < m; i++) {
16 int a, b;
17 cin >> a >> b;
18 G.add_edge(a, b);
19 }
20 auto ans = G.scc();
21 cout << ans.size() << '\n';
22 for (auto v : ans) {
23 cout << v.size();
24 for (int i : v) {
25 cout << ' ' << i;
26 }
27 cout << '\n';
28 }
29 return 0;
30}
H - Two SAT
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3#include <atcoder/all>
4using namespace std;
5using namespace atcoder;
6typedef long long ll;
7typedef pair<int, int> pii;
8#define pb push_back
9
10int main() {
11 ios::sync_with_stdio(0), cin.tie(0);
12 int n, d;
13 cin >> n >> d;
14 vector<int> a(n * 2);
15 two_sat ts(n * 2);
16 for (int i = 0; i < n; i++) {
17 cin >> a[i] >> a[i + n];
18 ts.add_clause(i, 1, i + n, 1);
19 }
20 for (int i = 0; i < 2 * n; i++) {
21 for (int j = i + 1; j < 2 * n; j++) {
22 if (abs(a[i] - a[j]) < d) {
23 ts.add_clause(i, 0, j, 0);
24 }
25 }
26 }
27 bool sat = ts.satisfiable();
28 if (sat) {
29 cout << "Yes\n";
30 } else {
31 cout << "No\n";
32 return 0;
33 }
34 auto ans = ts.answer();
35 for (int i = 0; i < n; i++) {
36 if (ans[i]) {
37 cout << a[i] << '\n';
38 } else {
39 cout << a[i + n] << '\n';
40 }
41 }
42 return 0;
43}