QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#735581#9459. Tree Equationzero-rangeAC ✓161ms19732kbC++231.6kb2024-11-11 20:48:562024-11-11 20:48:56

Judging History

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

  • [2024-11-11 20:48:56]
  • 评测
  • 测评结果:AC
  • 用时:161ms
  • 内存:19732kb
  • [2024-11-11 20:48:56]
  • 提交

answer

#include<stdio.h>
#include<algorithm>
#include<random>
#include<map>
#include<time.h>
#define M 100005
using namespace std;
typedef unsigned long long ull;
inline ull trans(ull x){
	x^=(x>>29)&0x5555555555555555ULL,
	x^=(x<<17)&0x71D67FFFEDA60000ULL,
	x^=(x<<37)&0xFFF7EEE000000000ULL,
	x^=(x>>43);
	return x;
}
struct Tree{
	int n,f[M],sz[M],dep[M],mxd;
	ull H[M];
	inline void read(){
		for(int i=1;i<=n;++i) scanf("%d",f+i),sz[i]=0;
		for(int i=n;i;--i) ++sz[i],sz[f[i]]+=sz[i];
		mxd=0;
		for(int i=1;i<=n;++i) dep[i]=dep[f[i]]+1,mxd=max(mxd,dep[i]);
	}
	inline void work(ull w){
		for(int i=1;i<=n;++i) H[i]=w;
		for(int i=n;i;--i) H[f[i]]+=trans(H[i]);
	}
} A,B,C;
vector<int> G[M];
map<ull,bool> sX,sY;
map<ull,int> mX,mY;
mt19937_64 rnd(time(0));
int tot;
void out(int x,int fa){
	printf("%d ",fa);
	int c=++tot;
	for(int p:G[x]) out(p,c);
}
inline void solve(){
	scanf("%d%d%d",&A.n,&B.n,&C.n);
	A.read(),B.read(),C.read();
	ull w=rnd();
	A.work(w),B.work(w),C.work(w),sX.clear(),sY.clear(),mX.clear(),mY.clear();
	for(int i=1;i<=C.n;++i){
		G[i].clear();	
		if(C.dep[i]==A.mxd&&!sX[C.H[i]]){
			sX[C.H[i]]=1,A.work(C.H[i]);
			mX[A.H[1]]=i;
		}
		if(C.dep[i]==B.mxd&&!sY[C.H[i]]){
			sY[C.H[i]]=1,B.work(C.H[i]);
			mY[B.H[1]]=i;
		}
		G[C.f[i]].push_back(i);
	}
	for(auto [Hx,x]:mX){
		ull Hy=C.H[1]+w-Hx;
		auto it=mY.find(Hy);
		if(it==mY.end()) continue;
		int y=it->second;
		printf("%d %d\n",C.sz[x],C.sz[y]);
		tot=0,out(x,0),putchar('\n'),
		tot=0,out(y,0),putchar('\n');
		return;
	}
	puts("Impossible");
}
int main(){
	// freopen("in.txt","r",stdin);
	int T;scanf("%d",&T);
	while(T--) solve();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10112kb

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: 161ms
memory: 19732kb

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: 2ms
memory: 10168kb

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