QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#636237#9459. Tree Equationucup-team296#AC ✓290ms200288kbC++204.3kb2024-10-12 22:59:042024-10-12 22:59:06

Judging History

你现在查看的是测评时间为 2024-10-12 22:59:06 的历史记录

  • [2024-10-13 18:42:56]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:AC
  • 用时:304ms
  • 内存:200172kb
  • [2024-10-13 10:44:25]
  • hack成功,自动添加数据
  • (/hack/952)
  • [2024-10-12 22:59:06]
  • 评测
  • 测评结果:100
  • 用时:290ms
  • 内存:200288kb
  • [2024-10-12 22:59:04]
  • 提交

answer

#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

long START = 4523124345423234234LL;
long MULT = 4827364237842376281LL;
long XOR = 843233513624273423LL;

struct node {
    int sz = 0;
    long hash = 0;
    vector<node *> ch;
};

void recalc(node *x) {
    vector<long> ch;
    x->sz = 1;
    for (auto y: x->ch) {
        ch.push_back(y->hash);
        x->sz += y->sz;
    }
    sort(ch.begin(), ch.end());
    x->hash = START;
    for (auto t: ch) {
        x->hash *= MULT;
        x->hash += t;
    }
    x->hash ^= XOR;
}

void build(node *x) {
    for (auto y: x->ch) {
        build(y);
    }
    recalc(x);
}

node *read_tree(int n) {
    vector<node *> t(n);
    for (int i = 0; i < n; i++) {
        t[i] = new node();
        int x;
        cin >> x;
        if (x > 0) {
            t[x - 1]->ch.push_back(t[i]);
        }
    }
    build(t[0]);
    return t[0];
}

node *max_child(node *c) {
    node *mc = nullptr;
    for (auto v: c->ch) {
        if (mc == nullptr || v->sz > mc->sz) {
            mc = v;
        }
    }
    return mc;
}

node *mult(node *a, node *b) {
    node *r = new node();
    for (auto v: b->ch)
        r->ch.push_back(v);
    for (auto v: a->ch)
        r->ch.push_back(mult(v, b));
    recalc(r);
    return r;
}

void build(node *x, int pp, vector<int> &p) {
    p.push_back(pp);
    int xx = p.size();
    for (auto v: x->ch) {
        build(v, xx, p);
    }
}

struct test {

    vector<int> resx, resy;

    void solve(node *a, node *b, node *c) {
        node *mc = max_child(c);
        node *ma = max_child(a);
        if (mc == nullptr) return;
        if (ma == nullptr) return;
        if (mc->sz % ma->sz != 0) return;
        int nx = mc->sz / ma->sz;
        node *x = new node();
        for (auto v: mc->ch) {
            if (v->sz < nx) {
                x->ch.push_back(v);
            }
        }
        recalc(x);
        if (x->sz != nx) return;
        node *aa = mult(a, x);
//        if (aa->hash != a->hash) return;
        map<long, vector<node *> > cc;
        for (auto v: c->ch) {
            cc[v->hash].push_back(v);
        }
        for (auto v: aa->ch) {
            if (cc[v->hash].empty()) return;
            cc[v->hash].pop_back();
        }
        node *c2 = new node();
        for (auto &[p, q] : cc) {
            for (auto v : q) {
                c2->ch.push_back(v);
            }
        }
        recalc(c2);

        mc = max_child(c2);
        ma = max_child(b);
        if (mc == nullptr) return;
        if (ma == nullptr) return;
        if (mc->sz % ma->sz != 0) return;
        int ny = mc->sz / ma->sz;
        node *y = new node();
        for (auto v: mc->ch) {
            if (v->sz < ny) {
                y->ch.push_back(v);
            }
        }
        recalc(y);
        if (y->sz != ny) return;
        node *bb = mult(b, y);
//        if (aa->hash != a->hash) return;
        cc.clear();
        for (auto v: c2->ch) {
            cc[v->hash].push_back(v);
        }
        for (auto v: bb->ch) {
            if (cc[v->hash].empty()) return;
            cc[v->hash].pop_back();
        }
        node *c3 = new node();
        for (auto &[p, q] : cc) {
            for (auto v : q) {
                c3->ch.push_back(v);
            }
        }
        recalc(c3);

        if (c3->sz != 1) return;

        build(x, 0, resx);
        build(y, 0, resy);
    }

    void solve() {
        int na, nb, nc;
        cin >> na >> nb >> nc;
        node *a = read_tree(na);
        node *b = read_tree(nb);
        node *c = read_tree(nc);

        solve(a, b, c);
        if (resx.empty()) {
            solve(b, a, c);
            swap(resx, resy);
        }
        if (resx.empty()) {
            cout << "Impossible\n";
        } else {
            cout << resx.size() << " " << resy.size() << "\n";
            for (int x: resx) cout << x << " ";
            cout << "\n";
            for (int x: resy) cout << x << " ";
            cout << "\n";
        }
    }
};

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }

    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3500kb

input:

2
2 3 10
0 1
0 1 2
0 1 1 3 4 3 6 3 1 9
4 3 10
0 1 2 2
0 1 2
0 1 1 3 4 3 6 3 1 9

output:

Impossible
2 1
0 1 
0 

result:

ok 2 cases passed

Test #2:

score: 0
Accepted
time: 290ms
memory: 200288kb

input:

11122
3 3 11
0 1 1
0 1 1
0 1 1 1 4 4 1 1 8 8 1
7 2 10
0 1 2 2 2 1 1
0 1
0 1 2 1 1 5 5 5 1 1
7 8 14
0 1 2 1 1 1 1
0 1 2 1 1 1 1 1
0 1 1 3 1 1 1 1 1 1 1 11 1 1
4 8 11
0 1 1 1
0 1 1 1 1 1 6 6
0 1 1 1 1 1 6 6 1 1 1
3 4 13
0 1 1
0 1 1 1
0 1 1 3 1 5 1 1 8 1 10 1 12
11 2 14
0 1 2 1 4 4 4 1 1 1 1
0 1
0 1 1 ...

output:

3 1
0 1 1 
0 
1 2
0 
0 1 
1 1
0 
0 
1 1
0 
0 
2 2
0 1 
0 1 
1 2
0 
0 1 
1 5
0 
0 1 2 1 1 
1 1
0 
0 
8 2
0 1 1 3 3 3 1 1 
0 1 
1 1
0 
0 
4 1
0 1 1 1 
0 
3 1
0 1 1 
0 
5 1
0 1 2 1 1 
0 
1 1
0 
0 
1 1
0 
0 
1 1
0 
0 
1 1
0 
0 
2 1
0 1 
0 
5 1
0 1 1 1 1 
0 
1 1
0 
0 
1 3
0 
0 1 1 
1 2
0 
0 1 
3 1
0 1 1 ...

result:

ok 11122 cases passed

Test #3:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

1
5 5 49
0 1 1 3 1
0 1 2 1 2
0 1 2 3 4 1 6 7 8 9 1 11 12 13 14 11 16 17 18 19 1 21 22 23 24 1 26 26 1 1 30 31 31 30 30 35 36 36 35 30 40 41 41 40 1 45 46 46 45

output:

5 5
0 1 2 3 4 
0 1 2 2 1 

result:

ok 1 cases passed

Extra Test:

score: 0
Extra Test Passed