QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#441017 | #1082. Uniform Subtrees | stasio6 | AC ✓ | 1719ms | 146480kb | C++14 | 2.5kb | 2024-06-14 10:14:37 | 2024-06-14 10:14:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
vi hashes[100002];
unordered_map<int, pair<int, signed>> from;
int pod = 1019, mod1 = 1000000009, mod2 = 1000000033;
int append_hash(int h, int i) {
int h1 = h / mod2, h2 = h % mod2;
h1 *= pod;
h1 += i;
h1 %= mod1;
h2 *= pod;
h2 += i;
h2 %= mod2;
return h1 * mod2 + h2;
}
vector<signed> sons[100002];
void rek(int n) {
map<int, int> mapa;
for (auto v : sons[n]) {
rek(v);
for (auto h : hashes[v])
mapa[h]++;
}
for (auto [h, ile] : mapa) {
for (int i = 1; i <= ile; i++) {
auto nh = append_hash(h, i);
hashes[n].PB(nh);
from[nh] = {h, i};
}
}
hashes[n].PB(0);
// cerr << n << "n\n";
// for (auto h : hashes[n]) {
// cerr << h << " ";
// }
// cerr << "\n";
}
int idx = 1;
void parse(int v, int &i, string &slo) {
// cerr << v << " " << i << "\n";
i++;
while (slo[i] != ')') {
sons[v].PB(idx);
parse(idx++, i, slo);
}
i++;
}
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
while (true) {
string slo;
cin >> slo;
if (slo == "0")
break;
for (int i = 0; i < sz(slo); i++) {
sons[i].clear();
hashes[i].clear();
}
from.clear();
int i = 0; idx = 1;
parse(0, i, slo);
// for (int v = 0; v < idx; v++) {
// cout << v << ": ";
// for (auto s : sons[v]) {
// cout << s << " ";
// }
// cout << "\n";
// }
rek(0);
vector<vi> res;
for (auto h : hashes[0]) {
vi ciag;
while (h != 0) {
ciag.PB(from[h].SD);
h = from[h].FS;
}
ciag.PB(0);
res.PB(ciag);
}
sort(all(res));
for (auto r : res) {
for (auto num : r) {
cout << num << " ";
}
cout << "\n";
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1719ms
memory: 146480kb
input:
(((()))(()(()())())) (()) () ((()()()()())((((()))))((((()()()()()()))))) ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
output:
0 1 0 1 1 0 1 1 1 0 1 1 2 0 1 2 0 1 3 0 2 0 2 1 0 2 1 1 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 2 0 1 1 1 1 3 0 1 1 1 1 4 0 1 1 1 1 5 0 1 1 1 1 6 0 1 2 0 1 3 0 1 4 0 1 5 0 2 0 2 1 0 2 1 1 0 2 1 1 1 0 2 1 1 1 1 0 3 0 3 1 0 0 1 0 1 1 0 1 1 1 0 ...
result:
ok 34755 lines