QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#720522#9459. Tree EquationHollow_knight_AC ✓59ms40124kbC++142.4kb2024-11-07 13:07:562024-11-07 13:07:57

Judging History

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

  • [2024-11-07 13:07:57]
  • 评测
  • 测评结果:AC
  • 用时:59ms
  • 内存:40124kb
  • [2024-11-07 13:07:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=2e6+15;
inline ll read(){
	ll x=0;char f=1,c=getchar();
	while(c<48||c>57){if(c=='-')f=0;c=getchar();}
	while(c>=48&&c<=57){x=(x<<1)+(x<<3)+ll(c)-48;c=getchar();}
	return f==1?x:-x;
}
ll seed=19780823;
ll get(ll x){
	x^=x<<13,x^=x>>7,x^=x<<17;
	return x;
}
struct tree{
	int n,f[N];
	ll mxd,hf[N],dep[N],siz[N];
	void input(){for(int i=1;i<=n;++i){f[i]=read();}}
	void hsh(ll x){
		mxd=0;
		for(int i=1;i<=n;++i){hf[i]=x,siz[i]=1,dep[i]=dep[f[i]]+1,mxd=max(mxd,dep[i]);}
		for(int i=n;i>=2;--i){hf[f[i]]+=get(hf[i]),siz[f[i]]+=siz[i];}
	}
	ll val(){return hf[1];}
};
tree a,b,c;
int cnta,cntb,scnt,np[N],visp[N],ans[N];
void sol(int u){
	for(int i=1;i<=c.n;++i){np[i]=visp[i]=ans[i]=0;}
	scnt=0,np[u]=++scnt,ans[scnt]=0,visp[u]=1;
	for(int i=2;i<=c.n;++i){
		if(visp[c.f[i]]){
			np[i]=++scnt,ans[scnt]=np[c.f[i]],visp[i]=1;
		}
	}
	for(int i=1;i<=scnt;++i){printf("%d ",ans[i]);}
}
unordered_map<ll,bool>vwa,vwb;
struct Node{
	ll siz;
	int x;
	friend bool operator <(Node a,Node b){
		return a.siz<b.siz;
	}
}pa[N],pb[N];
int solve(){
	vwa.clear(),vwb.clear();
	cnta=0,cntb=0;
	a.n=read(),b.n=read(),c.n=read();
	a.input(),b.input(),c.input();
	a.hsh(seed),b.hsh(seed),c.hsh(seed);
	for(int i=1;i<=c.n;++i){
		if(c.dep[i]==a.mxd&&!vwa.count(c.hf[i])){pa[++cnta]=Node{c.siz[i],i},vwa[c.hf[i]]=1;}
		if(c.dep[i]==b.mxd&&!vwb.count(c.hf[i])){pb[++cntb]=Node{c.siz[i],i},vwb[c.hf[i]]=1;}
	}
	sort(pa+1,pa+cnta+1),sort(pb+1,pb+cntb+1);
	for(int j,u,v,i=1;i<=cnta;++i){
		if(a.n*pa[i].siz>c.siz[1]){break;}
		for(j=1;j<=cntb;++j){
			if(a.n*pa[i].siz+b.n*pb[j].siz-1<c.siz[1]){continue;}
			if(a.n*pa[i].siz+b.n*pb[j].siz-1>c.siz[1]){break;}
			u=pa[i].x,v=pb[j].x;
			a.hsh(c.hf[u]),b.hsh(c.hf[v]);
			if(a.val()+b.val()-seed==c.val()){
				printf("%lld %lld\n",c.siz[u],c.siz[v]);
				sol(u),putchar('\n'),sol(v);
				return 0;
			}
		}
	}
	printf("Impossible");
	return 0;
}
/*
4
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

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
*/
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=read();
	while(T--){
		solve();
		if(T!=0)printf("\n");
	}
	fclose(stdin),fclose(stdout);
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 59ms
memory: 40124kb

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:

1 3
0 
0 1 1 
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 
2 8
0 1 
0 1 1 3 3 3 1 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 
1 5
0 
0 1 1 1 1 
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: 30664kb

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