HackerEarth Meet people problem solution

In this HackerEarth Meet people problem solution, You are given a tree of N nodes and K people located on the tree. You are also given an array A of size K where A[i] indicates the location of the ith person.

Now, there is an emergency meeting so all K people want to meet as soon as possible at the same node. In one second, a person who is standing at the ith node can go to any adjacent node of the ith node (the person cannot stand at the ith node and he or she has to move).

You are required to print the minimum time to meet all K people at the same node. If it is impossible to meet all K people at one node, then print -1.

HackerEarth Meet people problem solution.

#include<bits/stdc++.h>
using namespace std;

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define double long double

#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()

#define ff first
#define ss second
#define mp make_pair
#define pii pair<int,int>

#define pb push_back
#define endl "n"

#define f(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)

#define bp __builtin_popcountll
#define inf 1e18

const int N=1e5+5;

int a[N];
vector<int> people;
vector<int> v[N];
int vis[N],lvl[N],dis[N];

void dfs(int x,int p)
{
    for(auto X:v[x])
    {
        if(X==p) continue;
        lvl[X] = lvl[x] + 1;
        lvl[X] %= 2; 
        dfs(X,x);
    }
}
void solve()
{
    int n,k;
    cin>>n>>k;
        
    for(ll i=1;i<=n;i++)   v[i].clear();
    memset(a,0,sizeof(a));
    people.clear();
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    memset(lvl,0,sizeof(lvl));
    for(int i=0;i<n-1;i++)
    {
        int t1,t2;
        cin>>t1>>t2;
        v[t1].pb(t2);
        v[t2].pb(t1);
    }
    for(int i=0;i<k;i++)
    {
        int tt;
        cin>>tt;
        a[tt] = 1;
        people.pb(tt);
    }
    dfs(1,0);
    int chk = lvl[people[0]];

    for(int i=0;i<k;i++)
    {
        if((lvl[people[i]])!=chk)
        {
            cout<<-1<<endl;
            return;
        }
    }
    int ans = 0;
    queue<int> q;
    q.push(1); vis[1] = 1;
    int last = 1;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        if(a[k]==1)
        {
            last = k;
        }
        for(auto X:v[k])
        {
            if(vis[X]==0)
            {
                vis[X] = 1;
                q.push(X);
            }
        }
    }

    memset(vis,0,sizeof(vis));
    q.push(last);
    vis[last] = 1;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        if(a[k]==1)
        {
            ans = max(ans,dis[k]);
        }
        for(auto X:v[k])
        {
            if(vis[X]==0)
            {
                vis[X] = 1;
                q.push(X);
                dis[X] = dis[k] + 1;
            }
        }
    }
    ans = ans/2;
    cout<<ans<<endl;

}

int main()
{
    
        
    int t=1;
    cin>>t;
    for(int tc=1;tc<=t;tc++)
    {
        // cout<<"Case #"<<tc<<": ";
        solve();
    }
    
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 14;

struct SecondMax {
    int a = INT_MIN, b = INT_MIN, c{};

    void add(int x, int cer) {
        if (x > a)
            b = a, a = x, c = cer;
        else
            b = max(b, x);
    }

    int get(int bad) {
        return bad == c ? b : a;
    }
} down[maxn];

int n, k, up[maxn], h[maxn];
vector<int> g[maxn];
bool mark[maxn];

void dfs_down(int v = 0, int p = -1) {
    if (mark[v])
        down[v].add(0, -1);
    for (auto u : g[v])
        if (u != p) {
            h[u] = h[v] + 1;
            dfs_down(u, v);
            down[v].add(down[u].a + 1, u);
        }
}

void dfs_up(int v = 0, int p = -1) {
    if (mark[v])
        up[v] = max(up[v], 0);
    for (auto u : g[v])
        if (u != p) {
            up[u] = max(down[v].get(u), up[v]) + 1;
            dfs_up(u, v);
        }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        fill(g, g + n, vector<int>());
        fill(mark, mark + n, false);
        fill(up, up + n, 0);
        fill(down, down + n, SecondMax());
        for (int i = 0; i < n - 1; ++i) {
            int v, u;
            cin >> v >> u;
            v--, u--;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        int marked[k];
        for (int i = 0; i < k; ++i) {
            int x;
            cin >> x;
            x--;
            marked[i] = x;
            mark[x] = true;
        }
        dfs_down();
        dfs_up();
        if (any_of(marked, marked + k, [&](int v) {
            return h[v] % 2 != h[marked[0]] % 2;
        })) {
            cout << "-1n";
            continue;
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; ++i) {
            ans = min(ans, max(down[i].a, up[i]));
        }
        cout << ans << 'n';
    }
}

coding problems