# DAA Mock 2 Question 1

unknown
c_cpp
2 months ago
1.7 kB
2
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
#define int long long

unordered_map<int, bool> vis;

int binarySearch(vector<int>& a, int l, int r, int root) {
while(r - l > 1) {
int m = (l + r) >> 1;
if(a[m] > root) {
r = m - 1;
}
else l = m;
}

if(a[r] <= root) {
return r;
}
else return l;
}

int createTree(vector<int>& a, int l, int r) {
if(l > r) return -1;
if(l == r) return r;

int root = r;
int idx = binarySearch(a, l, r - 1, a[r]);
int left = createTree(a, l, idx);
int right = createTree(a, idx + 1, r - 1);
if(left != -1) {
}
if(right != -1) {
}

return root;
}

signed main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n, z, zIdx; cin >> n >> z;
vector<int> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
if(a[i] == z) zIdx = i;
}

createTree(a, 0, n - 1);
queue<int> q;
vis[zIdx] = true;
q.push(zIdx);

int time = -1, ans = 1;
while(!q.empty()) {
int size = q.size();
ans = max(size, ans);
for(int i = 0; i < size; i++) {
int curr = q.front(); q.pop();
for(auto x : adj[curr]) {
if(!vis[x]) {
vis[x] = true;
q.push(x);
}
}
}
time++;
}
cout << time << ' ' << ans << '\n';
return 0 ;
}
```