結果
問題 |
No.1576 織姫と彦星
|
ユーザー |
![]() |
提出日時 | 2021-08-01 22:05:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 940 bytes |
コンパイル時間 | 2,317 ms |
コンパイル使用メモリ | 199,668 KB |
最終ジャッジ日時 | 2025-01-23 13:29:11 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 54 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) #define int long long static const int INF=1000000007; int cb(int i,int j){ int ck=(i^j); int cnt=0; while(ck){ cnt+=ck%2; ck/=2; } if(cnt==1||cnt==0) return 1; else return 0; } signed main(){ int n; cin>>n; int x[n+2]; cin>>x[0]>>x[n+1]; rep(i,n) cin>>x[i+1]; vector<int>a[n+2]; rep(i,n+2) rep(j,n+2){ if(i == j) continue; int cnt=0; if(cb(x[i],x[j])==1) a[i].push_back(j); } if(cb(x[0],x[n+1])==1){ cout<<0<<endl; return 0; } vector<int>d(n+2,INF); queue<int>que; que.push(0); d[0]=0; while(!que.empty()){ int u=que.front(); que.pop(); for(auto v:a[u]){ if(d[v] != INF) continue; d[v]=d[u]+1; que.push(v); } } if(d[n+1]==INF){ cout<<-1<<endl; return 0; } else{ cout<<d[n+1]-1<<endl; } return 0; }