P10774 BZOJ3563 DZY Loves Chinese

· · 题解

你可以在 P10075 的题解区或者 ix35 的集训队论文看到本题的正常做法。但是作为经过 SCOI D2T2 洗礼的成熟 OIer，我们要学会直接从输入里搞到答案。

注意到每行输入的第一个数是本行接下来输入的数的个数异或上一问的答案，而我们实际上知道本行接下来输入的数的个数，所以我们可以直接由此推出上一问的答案。因此除了最后一组询问以外，所有询问的答案都是可以由下一个询问的输入直接推出的。最后一组询问直接暴力即可。

代码写的有点丑。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q;
struct Edge {
    int u, v;
} e[500005];
char s[100005];
int k, p[18], pC;
int fa[100005], las;
int F(int u) { return fa[u] == u ? u : fa[u] = F(fa[u]); }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &e[i].u, &e[i].v);
    }
    scanf("%d", &q);
    cin.ignore();
    for (int i = 1; i <= q; i++) {
        cin.getline(s, 100000);
        stringstream ss(s);
        ss >> k;
        pC = 1;
        while (ss >> p[pC]) {
            pC++;
        }
        pC--;
        int x = k ^ pC;
        for (int j = 1; j <= pC; j++) p[j] ^= x;
        if (i > 1) {
            puts(x == las ? "Disconnected" : "Connected");
            las = x;
        }
    }
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        bool flg = true;
        for (int j = 1; j <= pC; j++) if (i == p[j]) flg = false;
        if (flg) fa[F(e[i].u)] = F(e[i].v);
    }
    for (int i = 1; i <= m; i++) if (F(i) != F(1)) return puts("Disconnected"), 0;
    puts("Connected");
    return 0;
}