QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714866 | #9459. Tree Equation | Zaunese | AC ✓ | 218ms | 23944kb | C++14 | 3.2kb | 2024-11-06 08:44:29 | 2024-11-06 08:44:30 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using llu=unsigned long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}
const int NV=1e5;
llu XS(llu x){
x^=x<<13;
x^=x>>7;
x^=x<<17;
return x*2+1;
}
namespace gph{
std::map<llu,int> mp,mp2;
std::vector<int> Ta[NV+5],Tb[NV+5],Tc[NV+5];
llu hc[NV+5];
int pa[NV+5],pb[NV+5],pc[NV+5],sc[NV+5];
void dfsc(int x){
++mp[hc[x]=1];
sc[x]=1;
for(int t:Tc[x]){
dfsc(t);
sc[x]+=sc[t];
}
std::sort(Tc[x].begin(),Tc[x].end(),[&](int u,int v){
return sc[u]<sc[v];});
for(int t:Tc[x]){
hc[x]*=XS(hc[t]);
++mp[hc[x]];
}
mp2[hc[x]]=x;
}
std::vector<llu> xx,yy,ax,ay;
llu dfsa(int x,const llu v){
llu ans=v;
for(int t:Ta[x]) ans*=XS(dfsa(t,v));
return ans;
}llu dfsb(int x,const llu v){
llu ans=v;
for(int t:Tb[x]) ans*=XS(dfsb(t,v));
return ans;
}void chka(llu v){
ax.push_back(v);
xx.push_back(dfsa(1,v));
}void chkb(llu v){
ay.push_back(v);
yy.push_back(dfsb(1,v));
}
int prc;
void print(int x,int p){
printf("%d ",p);
int y=++prc;
for(int t:Tc[x]) print(t,y);
}
}
namespace xm{
llu inv(llu x){llu y=x;for(int i=6;i--;) y*=2-x*y; return y;}
void _(){
int Na,Nb,Nc;
scanf("%d%d%d",&Na,&Nb,&Nc);
for(int i=1;i<=Na;++i){
scanf("%d",gph::pa+i);
if(i>1) gph::Ta[gph::pa[i]].push_back(i);
}
for(int i=1;i<=Nb;++i){
scanf("%d",gph::pb+i);
if(i>1) gph::Tb[gph::pb[i]].push_back(i);
}
for(int i=1;i<=Nc;++i){
scanf("%d",gph::pc+i);
if(i>1) gph::Tc[gph::pc[i]].push_back(i);
}
gph::dfsc(1);
for(auto p:gph::mp){
if(p.se>=Na-1){
gph::chka(p.fi);
}
if(p.se>=Nb-1){
gph::chkb(p.fi);
}
}
std::map<llu,llu>mp3;
for(int i=0;i<(int)gph::yy.size();++i)
mp3[gph::yy[i]]=gph::ay[i];
for(int i=0;i<(int)gph::xx.size();++i){
auto nx=gph::xx[i];
auto ny=gph::hc[1]*inv(nx);
if(mp3.count(ny)){
printf("%d %d\n",gph::sc[gph::mp2[gph::ax[i]]],
gph::sc[gph::mp2[mp3[ny]]]);
gph::prc=0;
gph::print(gph::mp2[gph::ax[i]],0); puts("");
gph::prc=0;
gph::print(gph::mp2[mp3[ny]],0); puts("");
goto clear;
}
}
puts("Impossible");
clear: for(int i=1;i<=Na;++i) gph::Ta[i].clear();
for(int i=1;i<=Nb;++i) gph::Tb[i].clear();
for(int i=1;i<=Nc;++i) gph::Tc[i].clear();
gph::mp.clear();
gph::mp2.clear();
gph::xx.clear();
gph::yy.clear();
gph::ax.clear();
gph::ay.clear();
}
}
int main(){
int t;
scanf("%d",&t);
while(t--) xm::_();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 12356kb
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: 218ms
memory: 23944kb
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: 12120kb
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