1 条题解
-
0

#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
- 上传者