QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722910#9459. Tree EquationChendaqianAC ✓442ms23496kbC++142.3kb2024-11-07 20:34:242024-11-07 20:34:25

Judging History

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

  • [2024-11-07 20:34:25]
  • 评测
  • 测评结果:AC
  • 用时:442ms
  • 内存:23496kb
  • [2024-11-07 20:34:24]
  • 提交

answer

// dadaaa QwQ
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e5+10;
ull seed=rnd();
ull geths(ull x) {
	return x*x*x*x+x*x*x*seed+x*x*seed*seed+x*seed*seed*seed+seed*seed*seed*seed;
}
int T,n[3],f[3][N];
vector<int> e[3][N];
int sum[N];
unordered_map<ull,int> mp;
unordered_map<ull,ull> vis[2];
unordered_map<ull,int> pid;
ull hs[N];
void dfs(int x) {
	sum[x]=1;
	for(int v:e[2][x]) {
		dfs(v);
		sum[x]+=sum[v];
	} 
	sort(e[2][x].begin(),e[2][x].end(),[&](int a,int b) {
		return sum[a]<sum[b];
	});
	hs[x]=0;
	mp[hs[x]]++;
	for(int v:e[2][x]) {
		hs[x]+=geths(hs[v]);
		mp[hs[x]]++;
	}
	pid[hs[x]]=x;
}
ull dfscalc(int Trr,int x,ull w) {
	ull res=w;
	for(int v:e[Trr][x]) {
		res+=geths(dfscalc(Trr,v,w));
	}
	return res;
}
vector<int> ans[2];
void print(int Trr,int x,int Fa) {
	ans[Trr].push_back(Fa);
	int Id=ans[Trr].size();
	for(int v:e[2][x]) print(Trr,v,Id);
}
int main() {
	// cerr<<seed<<"\n";
	cin>>T;
	for(int Test=1;Test<=T;Test++) {
		// cerr<<"Start\n";
		cin>>n[0]>>n[1]>>n[2];
		for(int Trr=0;Trr<3;Trr++) {
			for(int i=1;i<=n[Trr];i++) {
				cin>>f[Trr][i];
				e[Trr][f[Trr][i]].push_back(i);
			}
		}
		dfs(1);
		// for(int i=1;i<=n[2];i++) cerr<<hs[i]<<' ';
		// cerr<<'\n';
		for(auto i:mp) {
			if(i.second>=n[0]-1) {
				vis[0][dfscalc(0,1,i.first)]=i.first;
				// cerr<<0<<' '<<pid[i.first]<<'\n';
			}
			if(i.second>=n[1]-1) {
				vis[1][dfscalc(1,1,i.first)]=i.first;
				// cerr<<1<<' '<<pid[i.first]<<'\n';
			}
		}
		bool fl=0;
		for(auto i:vis[0]) {
			if(vis[1].find(hs[1]-i.first)!=vis[1].end()) {
				int rt[2]={pid[i.second],pid[vis[1][hs[1]-i.first]]};
				// cerr<<rt[0]<<' '<<rt[1]<<'\n';
				ans[0].clear(),ans[1].clear();
				print(0,rt[0],0),print(1,rt[1],0);
				cout<<ans[0].size()<<' '<<ans[1].size()<<'\n';
				for(int p:ans[0]) cout<<p<<' ';
				cout<<'\n';
				for(int p:ans[1]) cout<<p<<' ';
				cout<<'\n';
				fl=1;
				break;
			}
		}
		if(!fl) cout<<"Impossible\n";
		for(int Trr=0;Trr<3;Trr++) {
			for(int i=0;i<=n[Trr];i++) e[Trr][i].clear();
		}
		mp.clear();
		vis[0].clear(),vis[1].clear();
		pid.clear();
	}
	return 0;
}
/*
cd QOJ9459
g++ code.cpp -o code -std=c++14 -Wall -O2
./code
*/

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 442ms
memory: 23496kb

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: 3ms
memory: 11804kb

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