QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#632124#9459. Tree Equationucup-team4863#AC ✓224ms103584kbC++143.5kb2024-10-12 12:23:372024-10-13 18:42:26

Judging History

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

  • [2024-10-13 18:42:26]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:AC
  • 用时:224ms
  • 内存:103584kb
  • [2024-10-13 10:44:25]
  • hack成功,自动添加数据
  • (/hack/952)
  • [2024-10-12 12:23:38]
  • 评测
  • 测评结果:100
  • 用时:258ms
  • 内存:103740kb
  • [2024-10-12 12:23:37]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 224ms
memory: 103584kb

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: 0ms
memory: 3800kb

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