QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714866#9459. Tree EquationZauneseAC ✓218ms23944kbC++143.2kb2024-11-06 08:44:292024-11-06 08:44:30

Judging History

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

  • [2024-11-06 08:44:30]
  • 评测
  • 测评结果:AC
  • 用时:218ms
  • 内存:23944kb
  • [2024-11-06 08:44:29]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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