贴一下 Educational Codeforces Round 22 F题的代码:
const int N = 1e5 + 1;
struct UF
{
int f[N], rk[N], d[N], top;
pair<int*, int> S[3*N];
int F(int x, int& t)
{
return f[x] ? (t ^= d[x], F(f[x], t)) : x;
}
void merge(int x, int y, int t)
{
if (rk[x] > rk[y]) swap(x, y);
S[top++] = make_pair(f+x, f[x]);
f[x] = y;
S[top++] = make_pair(d+x, d[x]);
d[x] = t;
if (rk[x] == rk[y])
S[top++] = make_pair(rk+y, rk[y]++);
}
void retrace(int t)
{
while (top != t)
{
pair<int*, int>& o = S[--top];
*o.first = o.second;
}
}
} U;
struct Edge {
int x, y, L, R;
};
bool ans[N];
void solve(int l, int r, vector<Edge>& E)
{
if (E.empty()) return;
vector<Edge> a, b;
int tmp = U.top, m = (l+r)/2;
for (auto e : E)
{
if (e.L <= l && r <= e.R)
{
int dx = 0, dy = 0, x = U.F(e.x, dx), y = U.F(e.y, dy);
if (x == y)
{
if (dx == dy)
{
rep (i, l, r+1) ans[i] = false;
U.retrace(tmp);
return;
}
}
else
{
U.merge(x, y, dx ^ dy ^ 1);
}
}
else
{
if (e.L <= m) a.push_back(e);
if (e.R > m) b.push_back(e);
}
}
solve(l, m, a);
solve(m+1, r, b);
U.retrace(tmp);
}
map<pair<int, int>, int> S;
vector<Edge> E;
int main()
{
int n, q;
scanf("%d%d", &n, &q);
rep (i, 0, q)
{
pair<int, int> e;
scanf("%d%d", &e.first, &e.second);
if (e.first > e.second) swap(e.first, e.second);
if (S.count(e))
{
E.push_back((Edge){e.first, e.second, S[e], i-1});
S.erase(e);
}
else
{
S[e] = i;
}
}
for (auto t : S)
E.push_back((Edge){t.first.first, t.first.second, t.second, q-1});
rep (i, 0, q) ans[i] = true;
solve(0, q-1, E);
rep (i, 0, q) puts(ans[i] ? "YES" : "NO");
return 0;
}
|