QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721270#9459. Tree EquationSpadeA261AC ✓173ms22404kbC++172.4kb2024-11-07 15:43:442024-11-07 15:43:45

Judging History

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

  • [2024-11-07 15:43:45]
  • 评测
  • 测评结果:AC
  • 用时:173ms
  • 内存:22404kb
  • [2024-11-07 15:43:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template<class T1,class T2> bool cmax(T1& a,const T2& b){return a<b?a=b,1:0;}
template<class T1,class T2> bool cmin(T1& a,const T2& b){return b<a?a=b,1:0;}
#define fir(i,x,y,...) for(int i(x),##__VA_ARGS__;i<=(y);i++)
#define firr(i,x,y,...) for(int i(x),##__VA_ARGS__;i>=(y);i--)
#define fird(i,x,y,d,...) for(int i(x),##__VA_ARGS__;i<=(y);i+=(d))
#define firrd(i,x,y,d,...) for(int i(x),##__VA_ARGS__;i>=(y);i-=(d))
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define endl "\n"
#define ll long long
#define ull unsigned long long
int T;
bool _mul=1;
ll gcd(ll x,ll y){if(!y) return x;return gcd(y,x%y);}
ll power(ll b,ll p,ll mod){ll res=1;while(p){if(p&1) res=res*b%mod;b=b*b%mod;p>>=1;}return res;}
const int N=1e5+5,B=131;
int na,nb,nc;
vector<int> ea[N],eb[N],ec[N];
int siz[N],tot;
ull h[N];
unordered_map<ull,ull> mp,a,b,c;
ull hsh(ull x){return x*x*x*x+x*x*x*B+x*x*B*B+x*B*B*B+B*B*B*B;}
ull dfsa(int u,ull x)
{
	ull res=x;
	for(int v:ea[u]) res+=hsh(dfsa(v,x));
	return res;
}
ull dfsb(int u,ull x)
{
	ull res=x;
	for(int v:eb[u]) res+=hsh(dfsb(v,x));
	return res;
}
void dfsc(int u)
{
	siz[u]=1;
	for(int v:ec[u]) dfsc(v),siz[u]+=siz[v];
	sort(ec[u].begin(),ec[u].end(),[](int x,int y){return siz[x]<siz[y];});
	mp[0]++;
	for(int v:ec[u]) h[u]+=hsh(h[v]),mp[h[u]]++;
	c[h[u]]=u;
}
void print(int u,int fa=0)
{
	int res=++tot;
	cout<<fa<<" ";
	for(int v:ec[u]) print(v,res);
}
void solve()
{
	cin>>na>>nb>>nc;
	fir(i,1,na,x) cin>>x,ea[x].push_back(i);
	fir(i,1,nb,x) cin>>x,eb[x].push_back(i);
	fir(i,1,nc,x) cin>>x,ec[x].push_back(i);
	dfsc(1);
	for(auto [x,cnt]:mp)
	{
		if(cnt>=na-1) a[dfsa(1,x)]=x;
		if(cnt>=nb-1) b[dfsb(1,x)]=x;
	}
	bool flag=0;
	for(auto [x,y]:a) if(b.count(h[1]-x))
	{
		int ansx=c[y],ansy=c[b[h[1]-x]];
		cout<<siz[ansx]<<" "<<siz[ansy]<<endl;
		tot=0,print(ansx),cout<<endl;
		tot=0,print(ansy),cout<<endl;
		flag=1;
		break;
	}
	if(!flag) cout<<"Impossible"<<endl;
	fir(i,0,na) ea[i].clear();
	fir(i,0,nb) eb[i].clear();
	fir(i,0,nc) ec[i].clear(),h[i]=0;
	mp.clear(),a.clear(),b.clear(),c.clear();
	return;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin.tie(nullptr)->sync_with_stdio(false);
	if(_mul) cin>>T;
	else T=1;
	while(T--) solve();
	return 0;
}

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

详细

Test #1:

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

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: 173ms
memory: 22404kb

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: 2ms
memory: 10644kb

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