QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720138#9459. Tree EquationSai_tqwqAC ✓178ms35284kbC++141.8kb2024-11-07 10:50:072024-11-07 10:50:08

Judging History

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

  • [2024-11-07 10:50:08]
  • 评测
  • 测评结果:AC
  • 用时:178ms
  • 内存:35284kb
  • [2024-11-07 10:50:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define double long double
#define endl '\n'
const int B=131;
int rnd(int x){return x*x*x*x+x*x*x*B+x*x*B*B+x*B*B*B+B*B*B*B;}
int na,nb,nc,fa[100009],fb[100009],fc[100009],szc[100009],hc[100009],dfnc;
vector<int> ga[100009],gb[100009],gc[100009];
unordered_map<int,vector<int> > cf;
unordered_map<int,int> cx,cy,cnt;
void dfs(int u){
	szc[u]=1;hc[u]=0;
	for(int v:gc[u])dfs(v),szc[u]+=szc[v];
	sort(gc[u].begin(),gc[u].end(),[&](int x,int y){return szc[x]<szc[y];});
	cnt[0]++;
	for(int v:gc[u])cnt[hc[u]+=rnd(hc[v])]++;
	cf[hc[u]].push_back(u);
}
int mula(int u,int x){int res=x;for(int v:ga[u])res+=rnd(mula(v,x));return res;}
int mulb(int u,int x){int res=x;for(int v:gb[u])res+=rnd(mulb(v,x));return res;}
void print(int u,int f){cout<<f<<' ';int p=++dfnc;for(int v:gc[u])print(v,p);}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int cas;cin>>cas;
	while(cas--){
		cin>>na>>nb>>nc;
		cf.clear();cx.clear();cy.clear();cnt.clear();
		for(int i=1;i<=na;i++)ga[i].clear(),cin>>fa[i];
		for(int i=1;i<=nb;i++)gb[i].clear(),cin>>fb[i];
		for(int i=1;i<=nc;i++)gc[i].clear(),cin>>fc[i];
		for(int i=1;i<=na;i++)ga[fa[i]].push_back(i);
		for(int i=1;i<=nb;i++)gb[fb[i]].push_back(i);
		for(int i=1;i<=nc;i++)gc[fc[i]].push_back(i);
		dfs(1);
		for(auto p:cnt){
			if(p.second>=na-1)cx[mula(1,p.first)]=p.first;
			if(p.second>=nb-1)cy[mulb(1,p.first)]=p.first;
		}
		bool fl=0;
		for(auto p:cx){
			int rx=hc[1]-p.first;
			if(cy.count(rx)){
				int x=cf[p.second][0],y=cf[cy[rx]][0];
				cout<<szc[x]<<' '<<szc[y]<<endl;
				dfnc=0;print(x,0);cout<<endl;
				dfnc=0;print(y,0);cout<<endl;
				fl=1;break;
			}
		}
		if(!fl)cout<<"Impossible\n";
	}
	return 0;
}

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

詳細信息

Test #1:

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

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: 178ms
memory: 35284kb

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

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