QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#634209#9459. Tree Equationucup-team087#AC ✓221ms22044kbC++149.8kb2024-10-12 16:53:052024-10-12 16:53:09

Judging History

你现在查看的是测评时间为 2024-10-12 16:53:09 的历史记录

  • [2024-10-13 18:42:31]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:AC
  • 用时:225ms
  • 内存:22140kb
  • [2024-10-13 10:44:25]
  • hack成功,自动添加数据
  • (/hack/952)
  • [2024-10-12 16:53:09]
  • 评测
  • 测评结果:100
  • 用时:221ms
  • 内存:22044kb
  • [2024-10-12 16:53:05]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
// 2^61 - 1 = 2'305'843'009'213'693'951
struct ModLong61 {
  static constexpr unsigned long long M = (1ULL << 61) - 1;
  unsigned long long x;
  constexpr ModLong61() : x(0ULL) {}
  constexpr ModLong61(unsigned x_) : x(x_) {}
  constexpr ModLong61(unsigned long long x_) : x(x_ % M) {}
  constexpr ModLong61(int x_) : x((x_ < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  constexpr ModLong61(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModLong61 &operator+=(const ModLong61 &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModLong61 &operator-=(const ModLong61 &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModLong61 &operator*=(const ModLong61 &a) {
    const unsigned __int128 y = static_cast<unsigned __int128>(x) * a.x;
    x = (y >> 61) + (y & M);
    x = (x >= M) ? (x - M) : x;
    return *this;
  }
  ModLong61 &operator/=(const ModLong61 &a) { return (*this *= a.inv()); }
  ModLong61 pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModLong61 a = *this, b = 1ULL; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModLong61 inv() const {
    unsigned long long a = M, b = x; long long y = 0, z = 1;
    for (; b; ) { const unsigned long long q = a / b; const unsigned long long c = a - q * b; a = b; b = c; const long long w = y - static_cast<long long>(q) * z; y = z; z = w; }
    assert(a == 1ULL); return ModLong61(y);
  }
  ModLong61 operator+() const { return *this; }
  ModLong61 operator-() const { ModLong61 a; a.x = x ? (M - x) : 0ULL; return a; }
  ModLong61 operator+(const ModLong61 &a) const { return (ModLong61(*this) += a); }
  ModLong61 operator-(const ModLong61 &a) const { return (ModLong61(*this) -= a); }
  ModLong61 operator*(const ModLong61 &a) const { return (ModLong61(*this) *= a); }
  ModLong61 operator/(const ModLong61 &a) const { return (ModLong61(*this) /= a); }
  template <class T> friend ModLong61 operator+(T a, const ModLong61 &b) { return (ModLong61(a) += b); }
  template <class T> friend ModLong61 operator-(T a, const ModLong61 &b) { return (ModLong61(a) -= b); }
  template <class T> friend ModLong61 operator*(T a, const ModLong61 &b) { return (ModLong61(a) *= b); }
  template <class T> friend ModLong61 operator/(T a, const ModLong61 &b) { return (ModLong61(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModLong61 &a) const { return (x == a.x); }
  bool operator!=(const ModLong61 &a) const { return (x != a.x); }
  bool operator<(const ModLong61 &a) const { return (x < a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModLong61 &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

#include <chrono>
#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif

////////////////////////////////////////////////////////////////////////////////

using Mint = ModLong61;

vector<Mint> R;

struct Tree {
  int n;
  vector<int> par;
  
  vector<vector<int>> graph;
  vector<int> sz;
  vector<Mint> fs;
  int vm;
  
  void build() {
    graph.assign(n, {});
    for (int u = 1; u < n; ++u) graph[par[u]].push_back(u);
    sz.assign(n, 1);
    fs.assign(n, 1);
    for (int u = n; --u >= 0; ) {
      for (const int v : graph[u]) {
        sz[u] += sz[v];
        fs[u] *= fs[v];
      }
      fs[u] += R[sz[u]];
    }
    vm = -1;
    for (const int v : graph[0]) if (!~vm || sz[vm] < sz[v]) vm = v;
// cerr<<"vm = "<<vm<<", sz[vm] = "<<sz[vm]<<endl;
  }
  
  vector<int> oks;
  vector<Mint> gs, zs;
  
  void compute(int nz) {
    oks.assign(n, 0);
    gs.assign(n, 1);
    zs.assign(n, 1);
    for (int u = n; --u >= 0; ) if (sz[u] >= nz) {
      if ([&]() -> bool {
        for (const int v : graph[u]) if (sz[v] < nz) zs[u] *= fs[v];
        zs[u] += R[nz];
        int sum = nz;
        for (const int v : graph[u]) if (sz[v] >= nz) {
          if (!oks[v]) return false;
          if (zs[u] != zs[v]) return false;
          sum += sz[v];
          gs[u] *= gs[v];
        }
        if (sz[u] != sum) return false;
        assert(sum % nz == 0);
        gs[u] += R[sum / nz];
        return true;
      }()) {
        oks[u] = 1;
      }
    }
// cerr<<"[compute] "<<nz<<endl;
// cerr<<"  oks = "<<oks<<endl;
// cerr<<"  gs = "<<gs<<endl;
// cerr<<"  zs = "<<zs<<endl;
  }
  
  void dfs(int u, vector<int> &us) {
    us.push_back(u);
    for (const int v : graph[u]) dfs(v, us);
  }
  vector<int> recover(int u) {
    vector<int> us;
    dfs(u, us);
    sort(us.begin(), us.end());
    const int usLen = us.size();
    vector<int> ps(usLen, -1);
    for (int j = 1; j < usLen; ++j) {
      ps[j] = lower_bound(us.begin(), us.end(), par[us[j]]) - us.begin();
    }
    return ps;
  }
} T[3];

vector<int> ans[2];
bool solve(int ha) {
  const int hb = ha ^ 1;
// cerr<<COLOR("33")<<"[solve] "<<ha<<" "<<hb<<COLOR()<<endl;
  Tree &A = T[ha];
  Tree &B = T[hb];
  Tree &C = T[2];
  if (C.sz[C.vm] % A.sz[A.vm] != 0) return false;
  const int NX = C.sz[C.vm] / A.sz[A.vm];
  C.compute(NX);
  if (!C.oks[C.vm]) return false;
  const Mint X = C.zs[C.vm];
  int ux = -1;
  for (int u = 0; u < C.n; ++u) if (C.fs[u] == X) { ux = u; break; }
  assert(~ux);
// cerr<<"NX = "<<NX<<", ux = "<<ux<<endl;
  
  vector<int> used(C.n, 0);
  
  vector<Mint> tar;
  vector<pair<Mint, int>> cs;
  auto cut = [&]() -> bool {
    sort(tar.begin(), tar.end());
    sort(cs.begin(), cs.end());
// cerr<<"[cut] "<<tar<<" "<<cs<<endl;
    const int tarLen = tar.size();
    const int csLen = cs.size();
    int i = 0;
    for (int j = 0; j < csLen; ++j) {
      if (i < tarLen && tar[i] == cs[j].first) {
        used[cs[j].second] = 1;
        ++i;
      }
    }
    return (i == tarLen);
  };
  
  tar.clear();
  cs.clear();
  for (const int v : A.graph[0]) tar.push_back(A.fs[v]);
  for (const int v : C.graph[0]) if (!used[v] && C.oks[v] && C.zs[v] == X) cs.emplace_back(C.gs[v], v);
  if (!cut()) return false;
  tar.clear();
  cs.clear();
  for (const int v : C.graph[ux]) tar.push_back(C.fs[v]);
  for (const int v : C.graph[0]) if (!used[v]) cs.emplace_back(C.fs[v], v);
  if (!cut()) return false;
// cerr<<"used = "<<used<<endl;
  
  int vmy = -1;
  for (const int v : C.graph[0]) if (!used[v]) if (!~vmy || C.sz[vmy] < C.sz[v]) vmy = v;
  if (!~vmy) return false;
  const int NY = C.sz[vmy] / B.sz[B.vm];
  C.compute(NY);
  if (!C.oks[vmy]) return false;
  const Mint Y = C.zs[vmy];
  int uy = -1;
  for (int u = 0; u < C.n; ++u) if (C.fs[u] == Y) { uy = u; break; }
  assert(~uy);
  
  tar.clear();
  cs.clear();
  for (const int v : B.graph[0]) tar.push_back(B.fs[v]);
  for (const int v : C.graph[0]) if (!used[v] && C.oks[v] && C.zs[v] == Y) cs.emplace_back(C.gs[v], v);
  if (!cut()) return false;
  tar.clear();
  cs.clear();
  for (const int v : C.graph[uy]) tar.push_back(C.fs[v]);
  for (const int v : C.graph[0]) if (!used[v]) cs.emplace_back(C.fs[v], v);
  if (!cut()) return false;
  
  for (const int v : C.graph[0]) if (!used[v]) return false;
  
  ans[ha] = T[2].recover(ux);
  ans[hb] = T[2].recover(uy);
  return true;
}

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    for (int h = 0; h < 3; ++h) {
      scanf("%d", &T[h].n);
      T[h].par.assign(T[h].n, -1);
    }
    for (int h = 0; h < 3; ++h) {
      for (int u = 0; u < T[h].n; ++u) {
        scanf("%d", &T[h].par[u]);
        --T[h].par[u];
      }
    }
    
    R.resize(T[2].n + 1);
    for (int s = 0; s <= T[2].n; ++s) R[s] = (unsigned long long)rng();
    for (int h = 0; h < 3; ++h) T[h].build();
    
    for (int h = 0; h < 2; ++h) ans[h].clear();
    bool res = false;
    for (int h = 0; h < 2; ++h) {
      res = solve(h);
      if (res) break;
    }
    
    if (res) {
      printf("%d %d\n", (int)ans[0].size(), (int)ans[1].size());
      for (int h = 0; h < 2; ++h) {
        for (int u = 0; u < (int)ans[h].size(); ++u) {
          if (u) printf(" ");
          printf("%d", ans[h][u] + 1);
        }
        puts("");
      }
    } else {
      puts("Impossible");
/*
cerr<<"FAIL"<<endl;
cerr<<T[0].n<<" "<<T[1].n<<" "<<T[2].n<<endl;
for(int h=0;h<3;++h){for(int u=0;u<T[h].n;++u)cerr<<T[h].par[u]+1<<" ";cerr<<endl;}
assert(false);
*/
    }
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 221ms
memory: 22044kb

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
0
1 4
0
0 1 1 1
1 4
0
0 1 1 1
1 2
0
0 1
1 3
...

result:

ok 11122 cases passed

Test #3:

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

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