QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714909#9459. Tree EquationDaiRuiChen007AC ✓215ms23592kbC++171.8kb2024-11-06 09:08:402024-11-06 09:08:41

Judging History

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

  • [2024-11-06 09:08:41]
  • 评测
  • 测评结果:AC
  • 用时:215ms
  • 内存:23592kb
  • [2024-11-06 09:08:40]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=1e5+5;
ull H(ull x) {
	auto _=[&](ull z) { return z*z*z+z*z*5+9*z+8; };
	return _(x>>32)+_(x&(-1u));
}
int na,nb,nc,fa[MAXN],fb[MAXN],fc[MAXN];
vector <int> A[MAXN],B[MAXN],C[MAXN];
int siz[MAXN];
ull f[MAXN];
map <ull,int> cnt;
void dfs1(int u) {
	siz[u]=1,f[u]=0;
	for(int v:C[u]) dfs1(v),siz[u]+=siz[v];
	sort(C[u].begin(),C[u].end(),[&](int x,int y){ return siz[x]<siz[y]; });
	++cnt[f[u]];
	for(int v:C[u]) f[u]+=H(f[v]),++cnt[f[u]];
}
ull dfs2(int u,ull w) {
	ull z=w;
	for(int v:A[u]) z+=H(dfs2(v,w));
	return z;
}
ull dfs3(int u,ull w) {
	ull z=w;
	for(int v:B[u]) z+=H(dfs3(v,w));
	return z;
}
void dfs4(int u,int fz,int &idx) {
	int x=++idx; cout<<fz<<" ";
	for(int v:C[u]) dfs4(v,x,idx);
}
void solve() {
	cin>>na>>nb>>nc,cnt.clear();
	for(int i=0;i<=na;++i) A[i].clear();
	for(int i=0;i<=nb;++i) B[i].clear();
	for(int i=0;i<=nc;++i) C[i].clear();
	for(int i=1;i<=na;++i) cin>>fa[i],A[fa[i]].push_back(i);
	for(int i=1;i<=nb;++i) cin>>fb[i],B[fb[i]].push_back(i);
	for(int i=1;i<=nc;++i) cin>>fc[i],C[fc[i]].push_back(i);
	dfs1(C[0][0]);
	map <ull,ull> ha,hb;
	for(auto it:cnt) {
		ull hv=it.first; int w=it.second;
		if(w>=na-1) ha[dfs2(A[0][0],hv)]=hv;
		if(w>=nb-1) hb[dfs3(B[0][0],hv)]=hv;
	}
	for(auto it:ha) {
		ull rem=f[C[0][0]]-it.first,tx=it.second;
		if(hb.count(rem)) {
			ull ty=hb[rem];
			int x=0,y=0;
			for(int i=1;i<=nc;++i) {
				if(f[i]==tx) x=i;
				if(f[i]==ty) y=i;
			}
			cout<<siz[x]<<" "<<siz[y]<<"\n";
			int cx=0,cy=0;
			dfs4(x,0,cx),cout<<"\n";
			dfs4(y,0,cy),cout<<"\n";
			return ;
		}
	}
	cout<<"Impossible\n";
	return ;
}
signed main() {
	ios::sync_with_stdio(false);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}

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

詳細信息

Test #1:

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

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: 215ms
memory: 23592kb

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