DAA Mock 2 Question 1

mail@pastecode.io avatar
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, vector<int>> adj;
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) {
        adj[root].push_back(left);
        adj[left].push_back(root);
    }
    if(right != -1) {
        adj[root].push_back(right);
        adj[right].push_back(root);
    }
    
    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 ;
}
Leave a Comment