1 条题解

  • 0
    @ 2026-1-12 1:22:27

    #include <bits/stdc++.h>
    #define EB emplace_back
    using std::cin;
    using std::cout;
    using std::vector;
    
    typedef unsigned long long u64;
    const int N = 108;
    const u64 multiplier = 2728434087ull, addend = 0xb7e151628aed2a6bull;
    
    int V;
    int o[N][N], p[N];
    u64 hasher[2][N][N], (*cur)[N] = *hasher, (*nxt)[N] = hasher[1];
    u64 seq[N], opt[N];
    vector <int> G[N], gr[N];
    vector <u64> repr[N];
    
    inline u64 next(u64 x) {return x ^= x << 13, x ^= x >> 7, x ^= x << 17, x * multiplier + addend;}
    
    int main() {
    	int i, j, k, u, v, l, $;
    	std::ios::sync_with_stdio(false), cin.tie(NULL);
    	memset(o, -1, sizeof o);
    	cin >> V;
    	for (i = 1; i <= V; ++i) {
    		cin >> l, G[i].reserve(l);
    		for (j = 0; j < l; ++j) cin >> v, o[i][v] = j, G[i].EB(v);
    		std::fill(nxt[i], nxt[i] + l, next(l));
    	}
    	for ($ = 0; $ < 128; ++$) {
    		std::swap(cur, nxt);
    		for (u = 1; u <= V; ++u) {
    			l = G[u].size();
    			for (i = 0; i < l; ++i) {
    				u64 &H = nxt[u][i]; H = next(cur[u][i]);
    				v = G[u][i], j = o[v][u], assert(~j);
    				for (k = j; k < (int)G[v].size(); ++k) H = next(H ^ cur[v][k]);
    				for (k = 0; k < j; ++k) H = next(H ^ cur[v][k]);
    			}
    		}
    	}
    	for (i = 1; i <= V; ++i) {
    		l = G[i].size(), memcpy(seq, nxt[i], l << 3), memcpy(opt, seq, l << 3);
    		for (j = 0; j < l; ++j) {
    			if (std::lexicographical_compare(opt, opt + l, seq, seq + l)) memcpy(opt, seq, l << 3);
    			std::rotate(seq, seq + 1, seq + l);
    		}
    		repr[i] = vector<u64>(opt, opt + l);
    	}
    	std::iota(p, p + V, 1), std::sort(p, p + V, [] (const int A, const int B) {return repr[A] < repr[B] || (repr[A] == repr[B] && A < B);});
    	for (k = j = i = 0; i < V; i = j) {
    		for (; j < V && repr[p[i]] == repr[p[j]]; ++j);
    		if (i + 1 < j) gr[k++] = vector<int>(p + i, p + j);
    	}
    	if (!k) return cout << "none\n", 0;
    	std::sort(gr, gr + k);
    	for (i = 0; i < k; ++i) {
    		$ = 1;
    		for (int x : gr[i]) ($ ? $ = 0, cout : cout << ' ') << x;
    		cout << '\n';
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    5741
    时间
    2000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者