JOI春18 3-1 Airline Route Map <Parallel>

解説の13ページ目あたりから分岐します

Aliceパート

元のグラフを とする。また、番目の頂点をとする。

まず、頂点を用意し、の全ての頂点と結ぶ。また、頂点を用意し、のビット目が立っているならばを結ぶ。 そして最後に、とを結ぶ。これでAliceパートは終わり

図示すればこのようになる。注意すべき点としては、の次数が必ずである点と、の次数が必ずである点だ。

Bobパート

まず、頂点としてあり得る候補は次数がである頂点のみである。(Aliceパートの作り方より、頂点数は決まる)

この候補を全て試し、矛盾が発生しないものを見つければよい。(実はここで2つ以上のグラフが発生しないとは言い切れないかも...)

とそれに直接つながっている頂点を除けば、11個の頂点が出てくる。この11個だけを取り出した時、パスグラフをなせば矛盾しない。ここで、はから最も遠い点であるので、そこから[B_{0}～B_{10}]まで確定させられる。 この復元はBFSを用いればできる。

あとは二進数の要領で復元し、まで重複なく1つずつ生成することができればよい。

コード

実装クソおもかった　微妙にTLEするが、vectorを生配列に変えるなど定数倍高速化を頑張ると通る。 atcoder.jp

#include "bits/stdc++.h"
#include "airline.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define vi vector<int>
#define all(a) a.begin(),a.end()
typedef pair<int,int> P;

void Alice( int N, int M, int A[], int B[] ){
    int V=N+12;
    vi c,d;
    rep(i,M){c.push_back(A[i]);d.push_back(B[i]);}
    rep(i,N){
        c.push_back(i);d.push_back(N);
    }
    rep(i,9){
        c.push_back(N+1+i);d.push_back(N+2+i);
    }
    for(int i=0;i<N;i++){
        rep(j,10){
            if(i&(1<<j)){
                c.push_back(i);
                d.push_back(N+1+j);
            }
        }
    }
    c.push_back(N+10);d.push_back(N+11);
    int U=c.size();
    InitG(V,U);
    rep(i,U){
        MakeG(i,c[i],d[i]);
    }
}
 
const int inf=1000000000;
 
vi G[1300];
int dist[1300],dist2[1300],revM[1300],checkcnt[11];
 
void bfs(int s){
    rep(i,1300)dist[i]=inf;
    dist[s]=0;
    queue<int>Q;
    Q.push(s);
    while(Q.size()){
        int v=Q.front();Q.pop();
        for(auto e:G[v]){
            if(dist[e]>dist[v]+1){
                dist[e]=dist[v]+1;
                Q.push(e);
            }
        }
    }
}
 
void Bob( int V, int U, int C[], int D[] ){
    rep(i,U){
        G[C[i]].push_back(D[i]);
        G[D[i]].push_back(C[i]);
    }   
    int N=V-12;
    vi cand;
    rep(i,V){
        if(G[i].size()==N){
            cand.push_back(i);
        }
    }
 
    for(auto star:cand){
        unordered_map<int,int>M;
        int flg=0;
        bfs(star);
        vector<P> di2;
        int di3=-1;
        rep(i,V){
            if(dist[i]>=2){
                di2.emplace_back(P(dist[i],i));
                M[i]=inf;
            }
        }
        M[star]=N;
        sort(all(di2));
        di3=di2[10].second;
        if(di2[10].first==di2[9].first)flg++;
 
        vector<int>another[1300];
        rep(i,U){
            if(M[C[i]]==inf&&M[D[i]]==inf){
                another[C[i]].emplace_back(D[i]);
                another[D[i]].emplace_back(C[i]);
            }
        }
    
        rep(i,V)dist2[i]=inf;
        dist2[di3]=0;
        queue<int>Q;
        Q.push(di3);
        while(Q.size()){
            int v=Q.front();Q.pop();
            for(auto e:another[v]){
                if(dist2[e]>dist2[v]+1){
                    dist2[e]=dist2[v]+1;
                    Q.push(e);
                }
            }
        }
 
    rep(j,11)checkcnt[j]=0;
        rep(i,V){
            if(dist2[i]<11){
                M[i]=11-dist2[i]+N;
                checkcnt[dist2[i]]++;
            }
        }
        
        rep(j,11){
            if(checkcnt[j]!=1)flg++;
            //cerr<<checkcnt[j]<<' ';
        }
        
        if(flg)continue;
 
    //復元パート
 
        rep(i,V){
            if(dist[i]==1){
                int res=0;
                for(auto e:G[i]){
                    if(M[e]>N)res+=1<<(M[e]-N-1);
                }
                M[i]=res;
            }
        }
        
    rep(i,V)revM[i]=-1;
        rep(i,V){
            if(revM[M[i]]!=-1)flg++;
            revM[M[i]]=i;
        }
        if(flg)continue;

        vi s,t;
        rep(i,U){
            C[i]=M[C[i]],D[i]=M[D[i]];
            if(C[i]<N&&D[i]<N){
                s.push_back(C[i]);
                t.push_back(D[i]);
            }
        }
        InitMap(N,s.size());
        rep(i,s.size()){
            MakeMap(s[i],t[i]);
        }
        return;
    }
}

感想

これ本番で7人も通してるの！？ヤバ過ぎ