QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#721807#9459. Tree EquationchrhaaAC ✓211ms25936kbC++143.2kb2024-11-07 16:54:412024-11-07 16:54:41

Judging History

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

  • [2024-11-07 16:54:41]
  • 评测
  • 测评结果:AC
  • 用时:211ms
  • 内存:25936kb
  • [2024-11-07 16:54:41]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int N=100005;

inline int read(){
	char c=getchar();
	int x=0;
	
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
		x=(x<<3)+(x<<1)+(c^48),c=getchar();

	return x;
}

#define ull unsigned long long
const ull B=233;

inline ull shift(ull x){
	x^=B;
	x^=x<<13;
	x^=x>>7;
	x^=x<<17;
	return x^B;
}

struct tree{
	int sz;
	ull h;

	inline tree operator+=(const tree x){
		sz+=x.sz;
		h+=shift(x.h);
		return *this;
	}

	inline bool operator<(const tree x)const{
		return sz==x.sz?h<x.h:sz<x.sz;
	}

	inline bool operator==(const tree x)const{
		return sz==x.sz&&h==x.h;
	}
};

#define vint vector<int>

int T,n,p,cnt,id[N],d[N];
bool vis[N];
tree t[N];
vint a,b,c,X,Y,ea[N],eb[N],ec[N];
vector<tree> h;
map<tree,int> m;

void dfs(int x,vint *e){
	if(d[x]>d[p]) p=x;

	for(int v:e[x]){
		d[v]=d[x]+1;
		dfs(v,e);
	}
}

void dfsX(int x){
	id[x]=++cnt;

	if(x!=p) X.push_back(id[c[x-1]]);
	else X.push_back(0);
	
	for(int v:ec[x]) dfsX(v);
}

void dfsY(int x){
	id[x]=++cnt;

	if(x!=p) Y.push_back(id[c[x-1]]);
	else Y.push_back(0);

	for(int v:ec[x]) dfsY(v);
}

tree calc1(int x,vint *e){
	vector<tree> f;
	tree res={1,1};

	for(int v:e[x]) f.push_back(calc1(v,e));

	sort(f.begin(),f.end());

	for(tree v:f) res+=v;

	return res;
}

tree calc2(int x,vint *e){
	vector<tree> f;
	tree res={1,1};

	for(int v:e[x]) f.push_back(calc2(v,e));
	for(tree v:h) f.push_back(v);

	sort(f.begin(),f.end());

	for(tree v:f) res+=v;

	return res;
}

bool solve(){
	int i,l;
	n=c.size();

	for(i=0;i<=n;i++){
		vis[i]=false;
		ea[i].clear();
		eb[i].clear();
		ec[i].clear();
	}

	for(i=1;i<a.size();i++) ea[a[i]].push_back(i+1);
	for(i=1;i<b.size();i++) eb[b[i]].push_back(i+1);
	for(i=1;i<c.size();i++) ec[c[i]].push_back(i+1);

	p=d[1]=0;
	dfs(1,ea);
	l=d[p];

	p=d[1]=0;
	dfs(1,ec);
	l=d[p]-l;
	
	if(l<0) return false;

	for(;l;l--) p=c[p-1];

	cnt=0;
	X.clear();
	dfsX(p);
	h.clear();

	for(int v:ec[p]) h.push_back(calc1(v,ec));

	m.clear();

	for(int v:ea[1]) m[calc2(v,ea)]++;
	for(tree v:h) m[v]++;

	vint tmp=ec[1];
	ec[1].clear();
	
	for(int v:tmp){
		tree w=calc1(v,ec);

		if(m[w]){
			m[w]--;
			vis[v]=true;
		}else ec[1].push_back(v);
	}

	for(auto _:m) if(_.second) return false;

	p=d[1]=0;
	dfs(1,eb);
	l=d[p];

	p=d[1]=0;
	dfs(1,ec);
	l=d[p]-l;
	
	if(l<0) return false;

	for(;l;l--) p=c[p-1];

	cnt=0;
	Y.clear();
	dfsY(p);
	h.clear();

	for(int v:ec[p]) h.push_back(calc1(v,ec));

	return calc2(1,eb)==calc1(1,ec);
}

void print(vint x,vint y){
	printf("%d %d\n",x.size(),y.size());

	for(int i=0;i<x.size();i++) printf("%d ",x[i]);

	puts("");
	
	for(int i=0;i<y.size();i++) printf("%d ",y[i]);

	puts("");
}

signed main(){
	for(int T=read(),i;T;T--){
		a.resize(read());
		b.resize(read());
		c.resize(read());

		for(i=0;i<a.size();i++) a[i]=read();
		for(i=0;i<b.size();i++) b[i]=read();
		for(i=0;i<c.size();i++) c[i]=read();

		if(solve()) print(X,Y);
		else{
			swap(a,b);

			if(solve()) print(Y,X);
			else puts("Impossible");
		}
	}

	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 211ms
memory: 25936kb

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:

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

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