QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#636237 | #9459. Tree Equation | ucup-team296# | AC ✓ | 290ms | 200288kb | C++20 | 4.3kb | 2024-10-12 22:59:04 | 2024-10-12 22:59:06 |
Judging History
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