QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717075#9459. Tree Equationbyron10000AC ✓175ms33912kbC++143.5kb2024-11-06 16:48:342024-11-06 16:48:34

Judging History

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

  • [2024-11-06 16:48:34]
  • 评测
  • 测评结果:AC
  • 用时:175ms
  • 内存:33912kb
  • [2024-11-06 16:48:34]
  • 提交

answer

#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define _UN using namespace
using namespace std;
const int MAXN=1e5+10;
typedef uint64_t Hash;
int _curcas;
Hash hash_(Hash x){ return _Hash_bytes(&x,sizeof(x),0xc70f6907ul); }
struct Tree{
    int n,mxdep; vector<int> G[MAXN];
    void clear(){
        RNG(u,1,n) G[u].clear();
        mxdep=0;
    }
    void dfs2(int u,int d){
        mxdep=max(mxdep,d);
        for(int v:G[u]) dfs2(v,d+1);
    }
    void init(){
        clear();
        RNG(u,1,n){
            int fa; cin>>fa;
            if(fa) G[fa].push_back(u);
        }
        dfs2(1,0);
    }
    Hash H[MAXN];
    void calc(int u,Hash a){
        H[u]=1+a;
        for(int v:G[u]) calc(v,a),H[u]+=hash_(H[v]);
    }
    int dfs1(const Tree& o,int ou){
        int u=++n;
        G[u]=o.G[ou];
        for(int& v:G[u]) v=dfs1(o,v);
        return u;
    }
    void copy(const Tree& o,int u){
        clear(); n=0;
        dfs1(o,u);
    }
    void dbg(){
        RNG(u,1,n){
            for(int v:G[u]) cerr<<u<<" "<<v<<"\n";
        }
        cerr<<"\n";
    }
    void print(){
        static int fa[MAXN];
        RNG(u,1,n){
            for(int v:G[u]) fa[v]=u;
        }
        RNG(u,1,n) cout<<fa[u]<<" ";
        cout<<"\n";
    }
} A,B,C,C1,X,Y;
void swap(Tree& a,Tree& b){
    swap(a.n,b.n),swap(a.mxdep,b.mxdep);
    RNG(i,1,max(a.n,b.n)) swap(a.G[i],b.G[i]);
}
int tp[MAXN];
void dfs1(int u,int d,int& mxd,int td,pair<int,int>& a){
    int mxd1=d;
    for(int v:C.G[u]){
        if(!tp[v]) dfs1(v,d+1,mxd1,td,a);
    }
    mxd=max(mxd,mxd1);
    if(d==td) a=max(a,pair<int,int>{mxd1,u});
}
bool solve(){
    fill_n(tp+1,C.n,0);
    C.calc(1,0);
    pair<int,int> a{0,0};
    { int _; dfs1(1,0,_,A.mxdep,a); }
    if(!a.second) return 0;
    X.copy(C,a.second);
    X.calc(1,0);
    A.calc(1,X.H[1]-1);
    auto match_edge=[](const Tree& T,int t)->bool{
        int c=0;
        unordered_map<Hash,int> mp;
        for(int u:T.G[1]) mp[T.H[u]]++,c++;
        for(int u:C.G[1]){
            if(!tp[u]){
                auto it=mp.find(C.H[u]);
                if(it!=mp.end()&&it->second>0) it->second--,c--,tp[u]=t;
            }
        }
        return !c;
    };
    bool flag=1;
    flag&=match_edge(X,1);
    flag&=match_edge(A,2);
    if(!flag) return 0;
    pair<int,int> b{0,0};
    { int _; dfs1(1,0,_,B.mxdep,b); }
    if(!b.second) return 0;
    Y.copy(C,b.second);
    Y.calc(1,0);
    B.calc(1,Y.H[1]-1);
    flag&=match_edge(Y,3);
    flag&=match_edge(B,4);
    if(!flag) return 0;
    for(int v:C.G[1]) flag&=!!tp[v];
    return flag;
}
void case_main(){
    cin>>A.n>>B.n>>C.n;
    A.init(),B.init(),C.init();
//  A.dbg(),B.dbg(),C.dbg();
    if(!solve()){
        swap(A,B);
        if(!solve()){ cout<<"Impossible\n"; return; }
        swap(X,Y);
    }
    cout<<X.n<<" "<<Y.n<<"\n";
    X.print(),Y.print();
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int cas; cin>>cas;
    RNG(_,1,cas) _curcas=_,case_main();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 175ms
memory: 33912kb

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 
8 2
0 1 1 3 3 3 1 1 
0 1 
1 1
0 
0 
4 1
0 1 1 1 
0 
3 1
0 1 1 
0 
5 1
0 1 2 1 1 
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 ...

result:

ok 11122 cases passed

Test #3:

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

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 2 2 1 

result:

ok 1 cases passed

Extra Test:

score: 0
Extra Test Passed