だいぶ手間取ってしまった。
https://codeforces.com/contest/1205/problem/B
問題
N頂点のグラフを考える。
N要素の整数列A[i]が与えられる。
A[i]とA[j]のbitwise-andが正であれば、頂点i,j間に辺があるとする。
最短の閉路長を求めよ。
解法
同じビットが立っている要素が3つ以上あれば、長さ3の閉路ができる。
そうでない場合、同じビットは2個以上たたないので、A[i]が0でない要素は120個程度しか現れない。
こうなると総当たりでDFSして閉路を求められる。
int N; ll A[101010]; int num[64]; vector<int> V[5000]; int mi=10101; int D[150][150][150]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>A[i]; if(A[i]==0) { i--; N--; continue; } FOR(x,62) if(A[i]&(1LL<<x)) { num[x]++; if(num[x]>=3) return _P("3\n"); } } FOR(x,N) FOR(y,N) { if(A[x]&A[y]) V[x].push_back(y); } FOR(i,N) FOR(j,N) FOR(k,N) D[i][j][k]=10101; queue<int> Q; FOR(i,N) { D[i][i][i]=0; Q.push(i*1000000+i*1000+i); } while(Q.size()) { int s=Q.front()/1000000; int pre=Q.front()/1000%1000; int cur=Q.front()%1000; Q.pop(); FORR(e,V[cur]) { if(e==pre || e==cur) continue; if(e==s) return _P("%d\n",D[s][pre][cur]+1); if(D[s][cur][e]>D[s][pre][cur]+1) { D[s][cur][e]=D[s][pre][cur]+1; Q.push(s*1000000+cur*1000+e); } } } cout<<-1<<endl; }
まとめ
なぜこんなかかってしまったのか。