QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722874#9459. Tree Equationdjh0314AC ✓135ms33100kbC++142.6kb2024-11-07 20:28:592024-11-07 20:28:59

Judging History

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

  • [2024-11-07 20:28:59]
  • 评测
  • 测评结果:AC
  • 用时:135ms
  • 内存:33100kb
  • [2024-11-07 20:28:59]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int N = 1e5+5;
const ull P = 131;
inline int read() {
	int x=0,f=1;
	char c=0;
	while(!isdigit(c=getchar())) if(c=='-') f=-f;
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x*f;
}
int n, m,na,nb;
int siz[N],dfn;
ull f[N];
vector<int> lj_a[N],lj_b[N],lj[N];
unordered_map<ull,vector<int> > id;
unordered_map<ull,ull> mark,vis,cnt;
inline bool cmp(int u,int v) {
	return siz[u]<siz[v];
}

inline ull Hsh(ull x) {
	x=x*x;
	return ((x>>3)^(x<<5))*P+((x<<7)^(x>>4))+P;
}

inline void dfs(int now) {
	siz[now]=1,f[now]=0;
	for(auto to:lj[now]) dfs(to),siz[now]+=siz[to];
	sort(lj[now].begin(),lj[now].end(),cmp);
	++cnt[0];
	for(auto to:lj[now]) f[now]+=Hsh(f[to]),cnt[f[now]]++;
	id[f[now]].push_back(now);
}

inline ull dfs_a(int now,int x) {
	ull res=x;
	for(auto to:lj_a[now]) res+=Hsh(dfs_a(to,x));
	return res;
}

inline ull dfs_b(int now,int x) {
	ull res=x;
	for(auto to:lj_b[now]) res+=Hsh(dfs_b(to,x));
	return res;
}

inline void print(int now,int fath) {
	cout<<fath<<" ";
	int id=++dfn;
	for(auto to:lj[now]) print(to,id);
}

inline void clear() {
	id.clear(),mark.clear(),vis.clear(),cnt.clear();
	for(int i=1; i<=na; ++i) lj_a[i].clear();
	for(int i=1; i<=nb; ++i) lj_b[i].clear();
	for(int i=1; i<=n; ++i) lj[i].clear();
}

inline void solve() {
//	cout<<"-------------------------------------------\n";
	clear();
	na=read(),nb=read(),n=read();
	for(int i=1; i<=na; ++i) lj_a[read()].push_back(i);
	for(int i=1; i<=nb; ++i) lj_b[read()].push_back(i);
	for(int i=1; i<=n; ++i) lj[read()].push_back(i);
	dfs(1);
	for(auto it:cnt) {
		int x=it.first,Cnt=it.second+1;
		if(Cnt>=na) mark[dfs_a(1,x)]=x;
		if(Cnt>=nb) vis[dfs_b(1,x)]=x;
	}
//	cout<<"--------------------------------------\n";
//	for(auto it:cnt) cout<<it.first<<" "<<it.second<<"\n";
//	cout<<"--------------------------------------\n";
//	for(auto it:mark) cout<<it.first<<" "<<it.second<<"\n";
//	cout<<"--------------------------------------\n";
//	for(auto it:vis) cout<<it.first<<" "<<it.second<<"\n";
//	cout<<"--------------------------------------\n";
	for(auto it:mark) {
		ull rx=f[1]-it.first;
		if(vis.count(f[1]-it.first)) {
			int u=id[it.second][0],v=id[vis[rx]][0];
//			int u=it.second,v=vis[f[1]-it.first];
//			u=id[u][0],v=id[v][0];
			cout<<siz[u]<<" "<<siz[v]<<"\n";
			dfn=0,print(u,0),puts("");
			dfn=0,print(v,0),puts("");
			return ;
		}
	}
	puts("Impossible");
}

signed main() {
	int T=read();
	while(T--) solve();
	return 0;
}

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

詳細信息

Test #1:

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

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: 135ms
memory: 33100kb

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: 11100kb

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