QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#715073#9459. Tree EquationguosounAC ✓186ms10324kbC++173.5kb2024-11-06 10:16:462024-11-06 10:16:47

Judging History

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

  • [2024-11-06 10:16:47]
  • 评测
  • 测评结果:AC
  • 用时:186ms
  • 内存:10324kb
  • [2024-11-06 10:16:46]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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