QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#715073 | #9459. Tree Equation | guosoun | AC ✓ | 186ms | 10324kb | C++17 | 3.5kb | 2024-11-06 10:16:46 | 2024-11-06 10:16:47 |
Judging History
answer
#include <bits/stdc++.h>
using ull = unsigned long long;
ull f(ull x) { return std::hash<std::bitset<64>>()(x); }
ull hash_tree(const std::vector<std::vector<int>> &son, int root, ull adt = 0) {
auto dfs = [&](auto &self, int u) -> ull {
ull ret = 1 + adt;
for (auto v : son[u]) ret += f(self(self, v));
return ret;
};
return dfs(dfs, root);
}
auto adjust(std::vector<std::vector<int>> &son) {
int n = son.size() - 1;
std::vector<int> siz(n + 1);
auto dfs = [&](auto &self, int u) -> void {
siz[u] = 1;
for (int v : son[u]) self(self, v), siz[u] += siz[v];
std::sort(son[u].begin(), son[u].end(),
[&](auto x, auto y) { return siz[x] < siz[y]; });
};
dfs(dfs, 1);
return siz;
}
std::vector<int> gen(const std::vector<std::vector<int>> &son,
std::vector<int> root) {
int n = son.size() - 1;
std::vector<int> id(n + 1);
id[0] = 1;
std::vector<int> ret{-1, 0};
auto dfs = [&](auto &self, int u, int ff) -> void {
id[u] = ret.size(), ret.push_back(id[ff]);
for (auto v : son[u]) self(self, v, u);
};
for (int v : root) dfs(dfs, v, 0);
ret[0] = ret.size() - 1;
return ret;
}
void mian() {
int na, nb, nc;
std::cin >> na >> nb >> nc;
std::vector<std::vector<int>> sa(na + 1), sb(nb + 1), sc(nc + 1);
for (int i = 1, p; i <= na; i++) std::cin >> p, sa[p].push_back(i);
for (int i = 1, p; i <= nb; i++) std::cin >> p, sb[p].push_back(i);
for (int i = 1, p; i <= nc; i++) std::cin >> p, sc[p].push_back(i);
auto solve =
[&]() -> std::optional<std::pair<std::vector<int>, std::vector<int>>> {
auto size_a = adjust(sa), size_c = adjust(sc);
if (size_c[sc[1].back()] % size_a[sa[1].back()]) return std::nullopt;
int size_x = size_c[sc[1].back()] / size_a[sa[1].back()] - 1;
if ((nc + 1 - na * (size_x + 1)) % nb) return std::nullopt;
int size_y = (nc + 1 - na * (size_x + 1)) / nb - 1;
ull hx = 0, hy = 0;
std::vector<int> retx, rety;
std::multiset<ull> s;
if (size_x) {
for (int t = size_x; int v : sc[sc[1].back()]) {
t -= size_c[v], hx += f(hash_tree(sc, v)), retx.push_back(v);
s.insert(hash_tree(sc, v));
if (t < 0) return std::nullopt;
if (t == 0) break;
}
}
for (int v : sa[1]) s.insert(hash_tree(sa, v, hx));
if (size_y) {
for (int t = size_y; int v : sc[1]) {
auto h = hash_tree(sc, v);
if (s.count(h)) {
s.erase(s.find(h));
continue;
}
t -= size_c[v], hy += f(hash_tree(sc, v)), rety.push_back(v);
if (t < 0) return std::nullopt;
if (t == 0) break;
}
}
if (hash_tree(sc, 1) != hash_tree(sa, 1, hx) + hash_tree(sb, 1, hy) - 1)
return std::nullopt;
return std::make_pair(retx, rety);
};
auto ret = solve();
if (!ret) {
std::swap(na, nb), std::swap(sa, sb);
ret = solve();
if (ret.has_value()) std::swap(ret.value().first, ret.value().second);
}
if (!ret)
std::cout << "Impossible\n";
else {
auto va = gen(sc, ret.value().first), vb = gen(sc, ret.value().second);
std::cout << va[0] << ' ' << vb[0] << '\n';
va.erase(va.begin()), vb.erase(vb.begin());
for (auto i : va) std::cout << i << ' ';
std::cout << '\n';
for (auto i : vb) std::cout << i << ' ';
std::cout << '\n';
}
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t;
std::cin >> t;
while (t--) mian();
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
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: 186ms
memory: 10324kb
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 1 1 4 1 1 0 0 8 2 0 1 1 1 1 5 5 5 0 1 1 1 0 0 4 1 0 1 1 1 0 3 1 0 1 1 0 5 1 0 1 1 1 4 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: 3544kb
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 1 3 3
result:
ok 1 cases passed
Extra Test:
score: 0
Extra Test Passed