QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#633387#9459. Tree Equationucup-team159#AC ✓240ms16144kbC++2010.3kb2024-10-12 15:13:392024-10-13 18:42:29

Judging History

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

  • [2024-10-13 18:42:29]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:AC
  • 用时:240ms
  • 内存:16144kb
  • [2024-10-13 10:44:25]
  • hack成功,自动添加数据
  • (/hack/952)
  • [2024-10-12 15:13:39]
  • 评测
  • 测评结果:100
  • 用时:231ms
  • 内存:16244kb
  • [2024-10-12 15:13:39]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < (t); ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define pob pop_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define newline puts("")
#define vc vector
using namespace std;
template<class T> using vv = vc<vc<T>>;
template<class T> using PQ = priority_queue<T,vc<T>,greater<T>>;
using uint = unsigned; using ull = unsigned long long;
using vi = vc<int>; using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>;
using P = pair<int,int>; using vp = vc<P>; using vvp = vv<P>; using LP = pair<ll,ll>;
int geti(){int x;scanf("%d",&x);return x;}
vi pm(int n, int s=0) { vi a(n); iota(rng(a),s); return a;}
template<class T1,class T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.fi>>v.se;}
template<class T1,class T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.fi<<","<<v.se;}
template<class T>istream& operator>>(istream&i,vc<T>&v){rep(j,sz(v))i>>v[j];return i;}
template<class T>string join(const T&v,const string&d=""){stringstream s;rep(i,sz(v))(i?s<<d:s)<<v[i];return s.str();}
template<class T>ostream& operator<<(ostream&o,const vc<T>&v){if(sz(v))o<<join(v," ");return o;}
template<class T>void vin(vc<T>&a){int n;cin>>n;a=vc<T>(n);cin>>a;}
template<class T>void vin(vv<T>&a){int n,m;cin>>n>>m;a=vv<T>(n,vc<T>(m));cin>>a;}
template<class T1,class T2>void operator--(pair<T1,T2>&a,int){a.fi--;a.se--;}
template<class T1,class T2>void operator++(pair<T1,T2>&a,int){a.fi++;a.se++;}
template<class T>void operator--(vc<T>&a,int){for(T&x:a)x--;}
template<class T>void operator++(vc<T>&a,int){for(T&x:a)x++;}
template<class T1,class T2>void operator+=(vc<T1>&a,T2 b){for(T1&x:a)x+=b;}
template<class T1,class T2>void operator-=(vc<T1>&a,T2 b){for(T1&x:a)x-=b;}
template<class T1,class T2>void operator*=(vc<T1>&a,T2 b){for(T1&x:a)x*=b;}
template<class T1,class T2>void operator/=(vc<T1>&a,T2 b){for(T1&x:a)x/=b;}
template<class T>void operator+=(vc<T>&a,const vc<T>&b){a.insert(a.end(),rng(b));}
template<class T1,class T2>pair<T1,T2>operator+(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi+b.fi,a.se+b.se};}
template<class T1,class T2>pair<T1,T2>operator-(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi-b.fi,a.se-b.se};}
template<class T>pair<T,T>operator*(const pair<T,T>&a,T b){return {a.fi*b,a.se*b};}
template<class T1,class T2>bool mins(T1& x,const T2&y){if(y<x){x=y;return true;}else return false;}
template<class T1,class T2>bool maxs(T1& x,const T2&y){if(x<y){x=y;return true;}else return false;}
template<class T>T min(const vc<T>&a){return *min_element(rng(a));}
template<class T>T max(const vc<T>&a){return *max_element(rng(a));}
template<class Tx,class Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;}
template<class T>ll suma(const vc<T>&a){ll s=0;for(auto&&x:a)s+=x;return s;}
template<class T>ll suma(const vv<T>&a){ll s=0;for(auto&&x:a)s+=suma(x);return s;}
template<class T>void uni(T&a){sort(rng(a));a.erase(unique(rng(a)),a.end());}
template<class T>void prepend(vc<T>&a,const T&x){a.insert(a.begin(),x);}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return;}
#define yes { puts("Yes"); return;}
#define no { puts("No"); return;}
#define rtn(x) { cout<<(x)<<'\n'; return;} // flush!
#define yn {puts("Yes");}else{puts("No");}
random_device _rd;
struct xrand {
  static const uint64_t _x = 88172645463325252ull;
  uint64_t x;
  xrand(): x(_x ^ (_rd()+time(0))) {}
  xrand(uint64_t seed): x(_x ^ seed) {}
  uint64_t get() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  ull operator()() { return get();}
  ull operator()(ull n) { return get()%n;}
  ll operator()(ll l, ll r) { return get()%(r-l+1) + l;}
} rnd;
template<typename T> void shuffle(vc<T>& a) {
  for (int i = a.size(); i >= 2; --i) swap(a[i-1],a[rnd(i)]);
}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}

// mod pair for hash
const int p1 = 33487;
struct mints {
  template<int mod>
  struct mint {
    uint x;
    mint(ull x=0):x(x%mod){}
    mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
    mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
    mint& operator*=(const mint& a) { x=(ull)x*a.x%mod; return *this;}
    mint& operator/=(const mint& a) { x=(ull)x*a.pow(mod-2).x%mod; return *this;}
    mint operator+(const mint& a)const{ return mint(*this) += a;}
    mint operator-(const mint& a)const{ return mint(*this) -= a;}
    mint operator*(const mint& a)const{ return mint(*this) *= a;}
    mint operator/(const mint& a)const{ return mint(*this) /= a;}
    bool operator<(const mint& a)const{ return x < a.x;}
    bool operator==(const mint& a)const{ return x == a.x;}
    mint pow(ll t) const {
      if(!t) return 1;
      mint res = pow(t/2);
      res *= res;
      return (t&1)?res*x:res;
    }
  };
  mint<1011235817> x;
  mint<987654347> y;
  mints(ll x=0):x(x),y(x){}
  mints& operator+=(const mints& a){ x+=a.x; y+=a.y; return *this;}
  mints& operator-=(const mints& a){ x-=a.x; y-=a.y;  return *this;}
  mints& operator*=(const mints& a){ x*=a.x; y*=a.y;  return *this;}
  mints& operator/=(const mints& a){ x/=a.x; y/=a.y;  return *this;}
  mints operator+(const mints& a)const{ return mints(*this) += a;}
  mints operator-(const mints& a)const{ return mints(*this) -= a;}
  mints operator*(const mints& a)const{ return mints(*this) *= a;}
  mints operator/(const mints& a)const{ return mints(*this) /= a;}
  bool operator<(const mints& a)const{ return (x==a.x)?(y<a.y):(x<a.x);}
  bool operator==(const mints& a)const{ return x==a.x && y==a.y;}
  ll get() const { return (ull)x.x<<32|y.x;}
};
ostream& operator<<(ostream&o,const mints&a){o<<a.x.x*ll(1e9)+a.y.x;return o;}
using vm = vector<mints>;
//

tuple<int,vvi,vi> ing(int n) {
  vvi to(n); vi pa(n);
  int rt = -1;
  rep(i,n) {
    int p;
    scanf("%d",&p);
    if (p == 0) rt = i, pa[i] = -1;
    else to[p-1].pb(i), pa[i] = p-1;
  }
  return {rt,to,pa};
}

struct Solver {
  void solve() {
    int na,nb,nc;
    scanf("%d%d%d",&na,&nb,&nc);
    auto [ra,ga,paa] = ing(na);
    auto [rb,gb,pab] = ing(nb);
    auto [rc,gc,pac] = ing(nc);

    vi depa(na), depb(nb), depc(nc);
    auto getdep = [&](vvi& g, int rt, vi& dep) {
      auto dfs = [&](auto f, int v) -> P {
        P res(0,v);
        for (int u : g[v]) maxs(res,f(f,u));
        dep[v] = res.fi;
        res.fi++;
        return res;
      };
      return dfs(dfs,rt).se;
    };
    getdep(ga,ra,depa);
    getdep(gb,rb,depb);
    int dv = getdep(gc,rc,depc);

    vm hsh(nc);
    rep(i,nc) hsh[i] = rnd();

    vm hc(nc);
    {
      auto dfs = [&](auto f, int v) -> mints {
        mints x = 1;
        for (int u : gc[v]) x *= f(f,u);
        x += hsh[depc[v]];
        return hc[v] = x;
      };
      dfs(dfs,rc);
    };
    vc<pair<ll,int>> chs;
    for (int ch : gc[rc]) chs.eb(hc[ch].get(),ch);
    sort(rng(chs));

    // cerr<<hc<<endl;

    rep(ab,2) {
      // cerr<<"ab: " << ab <<endl;
      if ([&] {
        if (depa[ra] > depc[rc]) return false;
        int rx = dv, depx = depc[rc]-depa[ra];
        rep(i,depx) rx = pac[rx];
        mints hx = hc[rx] - hsh[depc[rx]];

        // cerr<<rx<<endl;

        vm ha(na);
        {
          auto dfs = [&](auto f, int v) -> mints {
            mints x = hx;
            for (int u : ga[v]) x *= f(f,u);
            x += hsh[depa[v]+depx];
            return ha[v] = x;
          };
          dfs(dfs,ra);
        }
        // cerr<<hx<<endl;
        // cerr<<ha<<endl;

        vi used(nc);
        vl nchs;
        {
          vl nhs;
          for (int ch : ga[ra]) nhs.pb(ha[ch].get());
          for (int ch : gc[rx]) nhs.pb(hc[ch].get());
          sort(rng(nhs));
          int ni = 0;
          for (auto [nh,ch] : chs) {
            if (ni < sz(nhs) && nh == nhs[ni]) {
              ni++;
              used[ch] = 1;
            } else {
              nchs.eb(nh);
            }
          }
          if (ni != sz(nhs)) return false;
        }

        // cerr<<nchs<<endl;

        int ry = rc, ndep = 0;
        {
          while (1) {
            P mx(-1,-1);
            for (int ch : gc[ry]) if (!used[ch]) {
              maxs(mx,P(depc[ch],ch));
            }
            if (mx.fi == -1) break;
            ry = mx.se;
            ndep++;
          }
        }
        if (depb[rb] > ndep) return false;
        int depy = ndep-depb[rb];
        rep(i,depy) ry = pac[ry];
        mints hy = hc[ry] - hsh[depc[ry]];

        // cerr<<ry<<endl;

        vm hb(nb);
        {
          auto dfs = [&](auto f, int v) -> mints {
            mints x = hy;
            for (int u : gb[v]) x *= f(f,u);
            x += hsh[depb[v]+depy];
            return hb[v] = x;
          };
          dfs(dfs,rb);
        }
        {
          vl nhs;
          for (int ch : gb[rb]) nhs.pb(hb[ch].get());
          for (int ch : gc[ry]) nhs.pb(hc[ch].get());
          sort(rng(nhs));
          if (nhs != nchs) return false;
        }

        auto getans = [&](int rt) {
          vi ans;
          auto dfs = [&](auto f, int v, int pa=0) -> void {
            ans.pb(pa);
            int k = sz(ans);
            for (int u : gc[v]) f(f,u,k);
          };
          dfs(dfs,rt);
          return ans;
        };
        vi ansx = getans(rx);
        vi ansy = getans(ry);
        if (ab) swap(ansx,ansy);
        printf("%d %d\n",sz(ansx),sz(ansy));
        priv(ansx);
        priv(ansy);

        return true;
      }()) return;

      swap(na,nb);
      swap(ga,gb);
      swap(ra,rb);
      swap(paa,pab);
      swap(depa,depb);
    }

    puts("Impossible");
  }
};

int main() {
  // cin.tie(nullptr); ios::sync_with_stdio(false);
  int ts = 1;
  scanf("%d",&ts);
  rep1(ti,ts) {
    Solver solver;
    solver.solve();
  }
  return 0;
}

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

详细

Test #1:

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

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: 240ms
memory: 16144kb

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 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: 1ms
memory: 4148kb

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