fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8.  
  9.  
  10. void solve(){
  11. 	int n;
  12. 	cin >> n;
  13. 	vector<ll> a(n);
  14.  
  15. 	vector<vector<int>> c(70, vector<int>());
  16. 	vector<set<int>> g(n, set<int>());
  17. 	int ans = INT_MAX;
  18. 	for(int i = 0; i < n; i++){
  19. 		cin >> a[i];
  20. 		bitset<70> b(a[i]);
  21.  
  22. 		for(int j = 0; j < 70 && ans == INT_MAX; j++){
  23. 			if(b[j] == 1){
  24. 				for(auto x: c[j]){
  25. 					g[x].insert(i);
  26. 					g[i].insert(x);
  27. 				}
  28. 				c[j].push_back(i);
  29. 			}
  30. 			if(c[j].size() == 3){
  31. 				ans = 3;
  32. 			}
  33. 		}
  34. 	}
  35.  
  36.  
  37. 	if(ans == 3){
  38. 		cout << 3 << "\n";
  39. 		return;
  40. 	}
  41.  
  42.  
  43. 	auto bfs = [&](int x, int p) -> int {
  44.  
  45. 	    vector<int> dist(n, INT_MAX);
  46. 	    dist[x] = 0;
  47. 	    queue<int> q;
  48. 	    q.push(x);
  49.  
  50. 	    while(q.size()){
  51. 	    	int y = q.front();
  52. 	    	q.pop();
  53.  
  54. 	    	for(auto z: g[y]){
  55. 	    		if(dist[z] == INT_MAX){
  56. 	    			dist[z] = dist[y] + 1;
  57. 	    			if(z == p)return dist[z];
  58. 	    			q.push(z);
  59. 	    		}
  60. 	    	}
  61. 	    }
  62. 	    return INT_MAX - 1;
  63. 	};
  64.  
  65. 	for(int i = 0; i < n; i++){
  66. 		vector<int> q;
  67. 		for(auto x: g[i]){
  68. 			q.push_back(x);
  69. 		}
  70. 		for(auto x: q){
  71. 			g[i].erase(x);
  72. 			g[x].erase(i);
  73. 			ans = min(ans, bfs(i, x) + 1);
  74. 			g[i].insert(x);
  75. 			g[x].insert(i);
  76. 		}
  77. 	}
  78.  
  79.  
  80. 	if(ans != INT_MAX)cout << ans << "\n";
  81. 	else cout << -1 << "\n";
  82.  
  83.  
  84. } 
  85.  
  86. int main(){
  87. 	ios_base::sync_with_stdio(false);
  88. 	cin.tie(nullptr);
  89.  
  90. 	int t = 1;
  91. 	// cin >> t;
  92.  
  93. 	for(int i = 1; i <= t; i++){
  94. 		solve();
  95. 	}
  96. 	return 0;
  97. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
4
3 6 28 9
stdout
copy 
4
https://ideone.com/Hb15B1
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!