51 nodアルゴリズムマラソン29 C題美しい集合

原題リンク.
これは実は私が初めて計算してすぐに問題を出したのですが、私は弱すぎて、この問題を除いて、できません.
2つの集合を統合するたびに、実は1つの集合の要素を1つの集合に入れて01リュックサックを作ります.
集合合併があるなんて、明らかに啓発的に合併しなければならない.そうすれば、最大n log n要素が提案される.
しかし、暴力01リュックサックの毎回の複雑さが10^5であれば、受け入れがたい.
この01リュックサックは非常に特殊で、この体積にまとめることができるかどうかだけが要求されているので、これはブール値です.そこでbitsetは使えます.暴力が左に移動するたびに、上に上がればいいです.
複雑度O(nlog n mΩ)≒31250000
Code:

#include
#include
#include
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;

const int N = 1005;

int n, Q, z, x, y, a[N], s[N], f[N], d[N][N];
bitset<100001> b[1001], c, c2;

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

int main() {
    scanf("%d", &n);
    fo(i, 1, n) f[i] = i;
    fo(i, 1, n) scanf("%d", &a[i]), d[i][++ s[i]] = a[i], b[i][a[i]] = 1, b[i][0] = 1;
    for(scanf("%d", &Q); Q; Q --) {
        scanf("%d", &z);
        if(z == 1) {
            scanf("%d %d", &x, &y);
            if(find(x) == find(y)) continue;
            x = find(x); y = find(y);
            if(s[x] < s[y]) swap(x, y);
            fo(i, 1, s[y]) {
                c2 = b[x] << d[y][i];
                b[x] |= c2;
            }
            fo(i, 1, s[y]) d[x][++ s[x]] = d[y][i];
            f[y] = x;
        } else {
            scanf("%d", &x);
            x = find(x);
            printf("%d
", b[x].count());
        }
    }
}