This is my personal note and might be some kind of user editorial/learning material for some people. This is the second episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are completely solved by myself without looking at the editorial, that are both interesting and educational. If you want to motivate me to write a continuation (aka note 3), a significant upvote from you would be well appreciated!
(AC code)[https://mirror.codeforces.com/contest/1903/submission/236990689] <spoiler summary:"Code"> ```cpp //闲敲棋子落灯花//
include <bits/stdc++.h>
using namespace std; using i64 = long long;
const int NN = 6e5 + 500; stack s; int dfn[NN], low[NN], timer, cnt, col[NN]; bool vis[NN]; vector G[NN]; vector Neo[NN]; void tarjan(int u) { vis[u] = true; low[u] = dfn[u] = ++timer; s.push(u); for (auto v : Neo[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (vis[v]) { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]) { cnt++; while (1) { int x = s.top(); s.pop(); vis[x] = false; col[x] = cnt; if (x == u) break; } } }
int N, M; void add_edge(int x, int y) { Neo[x].push_back(y); return; } void build(int p, int l, int r) { if (l == r) { add_edge(p + 2 * N, l + N); return; } int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); add_edge(p + 2 * N, (p << 1) + 2 * N); add_edge(p + 2 * N, (p << 1 | 1) + 2 * N); return; } void add(int p, int l, int r, int ql, int qr, int x) { if (ql <= l && r <= qr) { add_edge(x, p + 2 * N); return; } int mid = (l + r) >> 1; if (ql <= mid) add(p << 1, l, mid, ql, qr, x); if (qr >= mid + 1) add(p << 1 | 1, mid + 1, r, ql, qr, x); return; } bool check(int k) { if (k == 1) return true; for (int i = 0; i <= 2 * N; i++) Neo[i].clear(); for (int i = 1; i <= N; i++) for (auto& v : G[i]) add_edge(i + N, v);
for (int i = 1; i <= N; i++) {
int L = max(1, i - k + 1), R = i - 1;
if (L <= R) add(1, 1, N, L, R, i);
L = i + 1; R = min(N, i + k - 1);
if (L <= R) add(1, 1, N, L, R, i);
}
while (s.size()) s.pop();
timer = 0, cnt = 0;
for (int i = 1; i <= 6 * N; i++)
low[i] = dfn[i] = vis[i] = 0;
for (int i = 1; i <= 6 * N; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= N; i++)
if (col[i] == col[i + N])
return false;
return true;} void solve() { cin >> N >> M; for (int i = 0; i <= 6 * N; i++) { G[i].clear(); Neo[i].clear(); } for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } build(1, 1, N); int l = 1, r = N; while (l < r) { int mid = (l + r + 1) >> 1; if (check(mid)) l = mid; else r = mid — 1; } cout << l << '\n'; return; }
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
solve();
}} ```
Comment on this problem and my feelings:
<spoiler summary:"Feelings"> This is the first time I saw a 2-SAT problem. Bruh I literally spent 1.5 hours to just read on 2-SAT. But the problem is amazing and interesting. Mixture of ideas (2-SAT, binary search and segment tree) was insane. Also, I submitted like 7 times like a dumbass before ACing.
Tips for implementation:
<spoiler summary:"Tips"> We can represent $$$i'$$$ as node with id $$$i + N$$$, also $$$tr_{L,R}$$$ with index $$$p$$$ in the segment tree with node with id $$$p+2*N$$$ for simpler implementation. Remember to clear all edges and the edges created from the previous check function (got like 4 WAs for this).
