QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#631968#9459. Tree Equationucup-team896#AC ✓200ms23504kbC++142.5kb2024-10-12 11:13:442024-10-13 18:42:26

Judging History

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

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

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
#define ull unsigned long long
int T,sza,szb,szc,fa_a[N],fa_b[N],fa_c[N];
vector<int>ea[N],eb[N],ec[N];int sz[N]; 
ull hsh_c[N];
map<ull,int>mp;
map<ull,ull>mp3;int cc;
map<ull,int>mp2;
ull XS(ull x){
    x^=x<<13;
    x^=x>>7;
    x^=x<<17;
    return x<<1|1;
}
bool cmp(int x,int y){
	return sz[x]<sz[y];
}
void dfs_c(int x){
    hsh_c[x]=1;
    sz[x]=1;
    mp[hsh_c[x]]++;
    for(int v:ec[x]){
    	dfs_c(v);
    	sz[x]+=sz[v];
	}
	sort(ec[x].begin(),ec[x].end(),cmp);
	for(int v:ec[x]){
		hsh_c[x]*=XS(hsh_c[v]);
		mp[hsh_c[x]]++;
//		mp2[hsh_c[x]]=-100;
	}
	mp2[hsh_c[x]]=x;
	// cout<<x<<" "<<hsh_c[x]<<endl;
    return;
}
vector<ull>xx,yy,ax,ay;
ull dfsa(int id,ull vl){
	ull nw=vl;
	for(auto v:ea[id]){
		nw*=XS(dfsa(v,vl));
	}
	return nw;
}
ull dfsb(int id,ull vl){
	ull nw=vl;
	for(auto v:eb[id]){
		nw*=XS(dfsb(v,vl));
	}
	return nw;
}
void check_a(ull vl){
	xx.push_back(dfsa(1,vl));
	ax.push_back(vl);
	return;
}
void check_b(ull vl){
	yy.push_back(dfsb(1,vl));
	ay.push_back(vl); 
	return;
}
void print(int x,int fa){
	cout<<fa<<' ';
	int y=++cc;
	for(auto v:ec[x])print(v,y);
}
ull inv(ull x) { ull y = x; for ( int i = 6 ; i-- ; ) y *= 2 - x * y; return y; }
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>sza>>szb>>szc;
		for(int i=1;i<=sza;i++){
			cin>>fa_a[i];
			if(i>1)ea[fa_a[i]].push_back(i);
		}
		for(int i=1;i<=szb;i++){
			cin>>fa_b[i];
			if(i>1)eb[fa_b[i]].push_back(i);
		}
		for(int i=1;i<=szc;i++){
			cin>>fa_c[i];
			if(i>1)ec[fa_c[i]].push_back(i);
		}
		dfs_c(1);
		for(auto x:mp){
			ull hsh=x.first;
			int cnt=x.second;
			if(cnt>=sza-1){
				check_a(hsh);
			}
			if(cnt>=szb-1){
				check_b(hsh);
			}
		}
		for(int i=0;i<yy.size();++i)mp3[yy[i]]=ay[i];
		bool ok=0;
		for(int i=0;i<xx.size();i++){
			ull nx=xx[i];
			ull ny=hsh_c[1]*inv(nx);
			if(mp3[ny]){
//				cout<<ax[i]<<endl;
				//cout<<mp3[ny]<<"+++\n";
				cout<<sz[mp2[ax[i]]]<<' '<<sz[mp2[mp3[ny]]]<<'\n';
				cc=0;
				print(mp2[ax[i]],0);cout<<'\n';
				cc=0;
				print(mp2[mp3[ny]],0);cout<<'\n';
				ok=1;
				break;
			}
		}
		if(!ok){
			cout<<"Impossible\n";
		}
		for(int i=1;i<=sza;i++){
			ea[i].clear();
		}
		for(int i=1;i<=szb;i++){
			eb[i].clear();
		}
		for(int i=1;i<=szc;i++){
			ec[i].clear();
		}
		mp.clear();
		mp2.clear();
		mp3.clear();
		xx.clear();
		yy.clear();
		ax.clear();
		ay.clear();
	}
	return 0;
} 

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

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 11860kb

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: 200ms
memory: 23504kb

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

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 1 3 3 

result:

ok 1 cases passed

Extra Test:

score: 0
Extra Test Passed