QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721103#9459. Tree EquationkonyakestAC ✓210ms22704kbC++172.9kb2024-11-07 15:15:292024-11-07 15:15:29

Judging History

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

  • [2024-11-07 15:15:29]
  • 评测
  • 测评结果:AC
  • 用时:210ms
  • 内存:22704kb
  • [2024-11-07 15:15:29]
  • 提交

answer

#include<bits/stdc++.h>
#define F(i,j,k) for(auto i=j;i<=(decltype(i))k;i++)
#define x first
#define y second
#define exec(...) [&](){__VA_ARGS__}()
#define endl '\n'
#define os ostream
#define pb push_back
#define view(x) begin(x),end(x)
#define lambda [&]
using namespace std;
using ll=long long;
template<typename T>void ckmin(T& x,T y){x=min(x,y);}
template<typename T>void ckmax(T& x,T y){x=max(x,y);}

#ifdef DEBUG
template<typename T1,typename T2>os& operator<<(os&,pair<T1,T2>);
template<typename T,typename=decltype(T().begin()),typename=enable_if_t<!is_same_v<decay_t<T>,string>>>os& operator<<(os& out,T x){auto n=0u;out<<"{";for(auto i:x) out<<i<<(++n==x.size()?"":",");return out<<"}";}
template<typename ...T>os& operator<<(os& out,tuple<T...> x){return apply(lambda(T... x){auto n=0u;out<<"{";((out<<x<<(++n==sizeof...(T)?"":",")),...);},x),out<<"}";}
template<typename T1,typename T2>os& operator<<(os& out,pair<T1,T2> x){return out<<tuple(x);}
#define debug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = "<<std::make_tuple(__VA_ARGS__)<<endl
#else
#define debug(...) (void)0
#endif

const int maxn=1e5+5;

vector<int> A[maxn],B[maxn],C[maxn];
int na,nb,nc,x,rta,rtb,rtc;

size_t gethsh(size_t x){return hash<bitset<64>>()(x);}

size_t get_hsh_sum(int u,size_t extra,vector<int> (&v)[maxn]){
	size_t ans=extra;
	for(auto i:v[u]) ans+=gethsh(get_hsh_sum(i,extra,v));
	return ans;
}

int siz[maxn];
size_t hsh[maxn];
map<size_t,int> cnt;
map<size_t,pair<int,int>> fn;

void init(int u){
	siz[u]=1;
	for(auto i:C[u]) init(i),siz[u]+=siz[i];
	sort(view(C[u]),lambda(int x,int y){return siz[x]<siz[y];});
	int tot=0;
	hsh[u]=0;
	cnt[0]++,fn[0]={u,-1};
	for(auto i:C[u]){
		hsh[u]+=gethsh(hsh[i]),cnt[hsh[u]]++;
		fn[hsh[u]]={u,tot++};
	}
}

void dfs(int u,int f,vector<int>& fn){
	fn.pb(f);
	int cur=fn.size();
	for(auto i:C[u]) dfs(i,cur,fn);
}

vector<int> getfn(size_t hsh){
	int u,i;
	tie(u,i)=fn[hsh];
	vector<int> fn={0};
	F(j,0,i) dfs(C[u][j],1,fn);
	return fn;
}

void solve(){
	init(rtc);
	map<size_t,size_t> all[2];
	for(auto i:cnt){
		if(i.y>=na-1) all[0][get_hsh_sum(rta,i.x,A)]=i.x;
		if(i.y>=nb-1) all[1][get_hsh_sum(rtb,i.x,B)]=i.x;
	}
	for(auto i:all[0]) if(all[1].count(hsh[rtc]-i.x)){
		debug(i.y,all[1][hsh[rtc]-i.x]);
		auto f1=getfn(i.y),f2=getfn(all[1][hsh[rtc]-i.x]);
		cout<<f1.size()<<" "<<f2.size()<<endl;
		for(auto i:f1) cout<<i<<" ";
		cout<<endl;
		for(auto i:f2) cout<<i<<" ";
		return;
	}
	cout<<"Impossible"<<endl;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--){
		F(i,1,na) A[i].clear();
		F(i,1,nb) B[i].clear();
		F(i,1,nc) C[i].clear();
		cnt.clear(),fn.clear();
		cin>>na>>nb>>nc;
		F(i,1,na) cin>>x,A[x].pb(i),(x==0)&&(rta=i);
		F(i,1,nb) cin>>x,B[x].pb(i),(x==0)&&(rtb=i);
		F(i,1,nc) cin>>x,C[x].pb(i),(x==0)&&(rtc=i);
		solve();
	}
}

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

详细

Test #1:

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

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: 210ms
memory: 22704kb

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

result:

ok 11122 cases passed

Test #3:

score: 0
Accepted
time: 2ms
memory: 10640kb

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