QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#441017#1082. Uniform Subtreesstasio6AC ✓1719ms146480kbC++142.5kb2024-06-14 10:14:372024-06-14 10:14:37

Judging History

你现在查看的是最新测评结果

  • [2024-06-14 10:14:37]
  • 评测
  • 测评结果:AC
  • 用时:1719ms
  • 内存:146480kb
  • [2024-06-14 10:14:37]
  • 提交

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