QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#632124 | #9459. Tree Equation | ucup-team4863# | AC ✓ | 258ms | 103740kb | C++14 | 3.5kb | 2024-10-12 12:23:37 | 2024-10-12 12:23:38 |
Judging History
answer
// created: 2024-10-12 11:41:23
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<vector>
#define F(i,l,r) for(int i=l,i##_end=r;i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
bool neg=false;int c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef unsigned long long ull;
ull rnd_f(ull x){return (6944339282543794533*x*x+5012652361889150211)*x+4978946612528691387;}
struct hash_t
{
ull a[4];
hash_t(){a[0]=2758805286833657955;a[1]=2343484460369680891;a[2]=7955642630093203468;a[3]=251359902938807085;}
void trans(){F(i,0,4)a[i]=rnd_f(a[i])^rnd_f(a[i]<<32^a[i]>>32);}
hash_t operator+=(const hash_t &v)
{
F(i,0,4)a[i]+=v.a[i];
return *this;
}
friend bool operator<(const hash_t &u,const hash_t &v){return memcmp(&u,&v,sizeof(hash_t))<0;}
friend bool operator!=(const hash_t &u,const hash_t &v){return memcmp(&u,&v,sizeof(hash_t));}
};
struct tree
{
int n;
vector<int> a;
tree():n(0),a(){}
void read(int n_)
{
a.resize(n=n_);
for(int &b:a)--::read(b);
}
void write()
{
for(int &b:a)printf("%d ",b+1);
puts("");
}
int height()
{
int h=0;
vector<int> d(n);
F(i,1,n)d[i]=d[a[i]]+1,h=max(h,d[i]);
return h;
}
tree extract(const vector<bool> &e)const
{
tree s;
F(i,0,n)if(e[i])++s.n;
s.a.reserve(s.n);
s.n=0;
vector<int> b(n);
F(i,0,n)if(e[i])s.a.emplace_back(i&&e[a[i]]?b[a[i]]:-1),b[i]=s.n++;
return s;
}
tree cut(int l)const
{
int u=0;
vector<int> d(n);
F(i,1,n)
{
d[i]=d[a[i]]+1;
if(d[i]>d[u])u=i;
}
if(d[u]<l)return tree();
vector<bool> e(n);
while(d[u]>l)u=a[u];
e[u]=true;
F(i,u+1,n)e[i]=e[a[i]];
return extract(e);
}
vector<pair<hash_t,int>> child()const
{
vector<hash_t> h(n);
vector<pair<hash_t,int>> c;
for(int i=n;--i;)
{
h[i].trans();
if(a[i])h[a[i]]+=h[i];
else c.emplace_back(h[i],i);
}
sort(c.begin(),c.end());
return c;
}
friend tree operator-(const tree &a,const tree &b)
{
vector<pair<hash_t,int>> ca=a.child(),cb=b.child();
vector<pair<hash_t,int>>::iterator ia=ca.begin(),ib=cb.begin();
vector<bool> e(a.n);
for(;ib!=cb.end();++ib)
{
while(ia!=ca.end()&&ia->first<ib->first)e[ia++->second]=true;
if(ia==ca.end()||ia->first!=ib->first)return tree();
++ia;
}
for(;ia!=ca.end();++ia)e[ia->second]=true;
F(i,1,a.n)e[i]=e[i]||e[a.a[i]];
e[0]=true;
return a.extract(e);
}
friend tree operator*(const tree &a,const tree &b)
{
tree c;c.n=a.n*b.n;c.a.resize(c.n);
F(i,0,a.n)
{
c.a[i*b.n]=i?a.a[i]*b.n:-1;
F(j,1,b.n)c.a[i*b.n+j]=i*b.n+b.a[j];
}
return c;
}
};
bool solve(tree a,tree b,tree c,bool rev=false)
{
tree x=c.cut(a.height());
if(!x.n)return false;
c=c-a*x;
if(!c.n)return false;
tree y=c.cut(b.height());
if(!y.n)return false;
c=c-b*y;
if(c.n!=1)return false;
if(rev)swap(x,y);
printf("%d %d\n",x.n,y.n);
x.write();y.write();
return true;
}
void solve()
{
int na,nb,nc;
tree a,b,c;
read(na,nb,nc);
a.read(na);
b.read(nb);
c.read(nc);
if(!(solve(a,b,c)||solve(b,a,c,true)))puts("Impossible");
}
int main()
{
int tt;read(tt);
while(tt--)solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
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: 258ms
memory: 103740kb
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: 1ms
memory: 3836kb
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