QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#720060#9459. Tree EquationPurslaneAC ✓156ms27864kbC++141.8kb2024-11-07 10:28:002024-11-07 10:28:00

Judging History

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

  • [2024-11-07 10:28:00]
  • 评测
  • 测评结果:AC
  • 用时:156ms
  • 内存:27864kb
  • [2024-11-07 10:28:00]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int T,a,b,n,tp[MAXN];
ull ha[MAXN],hb[MAXN],h[MAXN];
ull mask;
mt19937 myrand(time(NULL));
ull shift(ull x) {return x^=mask,x^=x<<13,x^=x>>7,x^=x<<17,x^=mask,x;}
struct Tree {
	vector<int> G[MAXN];
	int dep[MAXN],sze[MAXN];
	ull h[MAXN];
	void dfs(int u) {
		sze[u]=1,h[u]=1;
		for(auto v:G[u]) dep[v]=dep[u]+1,dfs(v),sze[u]+=sze[v],h[u]+=shift(h[v]);
		return ;
	}
	ull calc(int u,ull x) {
		ull ans=x;
		for(auto v:G[u]) ans+=shift(calc(v,x));
		return ans;	
	}
	void init(int n) {
		ffor(i,1,n) G[i].clear();
		ffor(i,1,n) {int f;cin>>f,G[f].push_back(i);}
		dfs(1);
		return ;
	}
	void output(int u,int fa,int &tot) {
		int id=++tot;
		cout<<fa<<' ';
		for(auto v:G[u]) output(v,id,tot);
		return ;
	}
}A,B,C;
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		mask=myrand()*myrand();
		cin>>a>>b>>n;
		A.init(a),B.init(b),C.init(n);
		int mxa=0,mxb=0;
		ffor(i,1,a) mxa=max(mxa,A.dep[i]);
		ffor(i,1,b) mxb=max(mxb,B.dep[i]);
		map<ull,int> mpa,mpb,usa,usb;
		ffor(i,1,n) if(C.dep[i]==mxa) {
			if(a<=n/C.sze[i]&&!usa[C.h[i]]) {
				usa[C.h[i]]=1;
				mpa[A.calc(1,C.h[i])]=i;	
			}
		}
		ffor(i,1,n) if(C.dep[i]==mxb) {
			if(b<=n/C.sze[i]&&!usb[C.h[i]]) {
				usb[C.h[i]]=1;
				mpb[B.calc(1,C.h[i])]=i;	
			}
		}
		int flg=0;
		for(auto pr:mpa) {
			ull val=pr.first,x=C.h[1]+1-val;
			if(mpb[x]) {
				int id1=pr.second,id2=mpb[x];
				cout<<C.sze[id1]<<' '<<C.sze[id2]<<'\n';
				int tot1=0,tot2=0;
				C.output(id1,0,tot1),cout<<'\n',C.output(id2,0,tot2);
				flg=1;break ;
			}
			//val+x=hsh[1]+1	
		}
		if(!flg) cout<<"Impossible\n";
	}
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 156ms
memory: 27864kb

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 2 1 1 1 1
0 
0 2 8
0 1 
0 1 1 3 3 3 1 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 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 
0 1 4
0 
0 1 1 1 1 4
...

result:

ok 11122 cases passed

Test #3:

score: 0
Accepted
time: 0ms
memory: 16124kb

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