QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#631968 | #9459. Tree Equation | ucup-team896# | AC ✓ | 200ms | 23504kb | C++14 | 2.5kb | 2024-10-12 11:13:44 | 2024-10-13 18:42:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
#define ull unsigned long long
int T,sza,szb,szc,fa_a[N],fa_b[N],fa_c[N];
vector<int>ea[N],eb[N],ec[N];int sz[N];
ull hsh_c[N];
map<ull,int>mp;
map<ull,ull>mp3;int cc;
map<ull,int>mp2;
ull XS(ull x){
x^=x<<13;
x^=x>>7;
x^=x<<17;
return x<<1|1;
}
bool cmp(int x,int y){
return sz[x]<sz[y];
}
void dfs_c(int x){
hsh_c[x]=1;
sz[x]=1;
mp[hsh_c[x]]++;
for(int v:ec[x]){
dfs_c(v);
sz[x]+=sz[v];
}
sort(ec[x].begin(),ec[x].end(),cmp);
for(int v:ec[x]){
hsh_c[x]*=XS(hsh_c[v]);
mp[hsh_c[x]]++;
// mp2[hsh_c[x]]=-100;
}
mp2[hsh_c[x]]=x;
// cout<<x<<" "<<hsh_c[x]<<endl;
return;
}
vector<ull>xx,yy,ax,ay;
ull dfsa(int id,ull vl){
ull nw=vl;
for(auto v:ea[id]){
nw*=XS(dfsa(v,vl));
}
return nw;
}
ull dfsb(int id,ull vl){
ull nw=vl;
for(auto v:eb[id]){
nw*=XS(dfsb(v,vl));
}
return nw;
}
void check_a(ull vl){
xx.push_back(dfsa(1,vl));
ax.push_back(vl);
return;
}
void check_b(ull vl){
yy.push_back(dfsb(1,vl));
ay.push_back(vl);
return;
}
void print(int x,int fa){
cout<<fa<<' ';
int y=++cc;
for(auto v:ec[x])print(v,y);
}
ull inv(ull x) { ull y = x; for ( int i = 6 ; i-- ; ) y *= 2 - x * y; return y; }
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>T;
while(T--){
cin>>sza>>szb>>szc;
for(int i=1;i<=sza;i++){
cin>>fa_a[i];
if(i>1)ea[fa_a[i]].push_back(i);
}
for(int i=1;i<=szb;i++){
cin>>fa_b[i];
if(i>1)eb[fa_b[i]].push_back(i);
}
for(int i=1;i<=szc;i++){
cin>>fa_c[i];
if(i>1)ec[fa_c[i]].push_back(i);
}
dfs_c(1);
for(auto x:mp){
ull hsh=x.first;
int cnt=x.second;
if(cnt>=sza-1){
check_a(hsh);
}
if(cnt>=szb-1){
check_b(hsh);
}
}
for(int i=0;i<yy.size();++i)mp3[yy[i]]=ay[i];
bool ok=0;
for(int i=0;i<xx.size();i++){
ull nx=xx[i];
ull ny=hsh_c[1]*inv(nx);
if(mp3[ny]){
// cout<<ax[i]<<endl;
//cout<<mp3[ny]<<"+++\n";
cout<<sz[mp2[ax[i]]]<<' '<<sz[mp2[mp3[ny]]]<<'\n';
cc=0;
print(mp2[ax[i]],0);cout<<'\n';
cc=0;
print(mp2[mp3[ny]],0);cout<<'\n';
ok=1;
break;
}
}
if(!ok){
cout<<"Impossible\n";
}
for(int i=1;i<=sza;i++){
ea[i].clear();
}
for(int i=1;i<=szb;i++){
eb[i].clear();
}
for(int i=1;i<=szc;i++){
ec[i].clear();
}
mp.clear();
mp2.clear();
mp3.clear();
xx.clear();
yy.clear();
ax.clear();
ay.clear();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 11860kb
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: 200ms
memory: 23504kb
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: 0ms
memory: 10704kb
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