HackerEarth Largest Windmill problem solution

In this HackerEarth Largest Windmill problem solution We define a windmill graph as a graph G centered on node c with at least 5 adjacent paths. One of these paths has to have length at least 3 and it is interpreted as the base of the windmill. The remaining paths have length exactly 1 and are interpreted as the sails of the windmill.
For a given tree T with N nodes, the goal is to find the size of its largest subgraph (in terms of the number of nodes) which is a windmill graph and it’s center vertex. If there are many such largest subgraphs, take the one with the smallest center vertex. If no windmill graph is a subgraph of T, then the answer is 1.

HackerEarth Largest Windmill problem solution.

`#include <iostream>#include <cstdio>#include <string>#include <sstream> #include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <cmath>#include <algorithm>#include <cstring>#include <ctime>#include <cassert>using namespace std;#define pb push_back#define mp make_pair#define pii pair<int,int>#define vi vector<int>#define SZ(x) ((int)(x.size()))#define fi first#define se second#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))#define IN(x,y) ((y).find((x))!=(y).end())#define ALL(t) t.begin(),t.end()#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)#define REMAX(a,b) (a)=max((a),(b));#define REMIN(a,b) (a)=min((a),(b));#define DBG cerr << "debug here" << endl;#define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;typedef long long ll;const int INF = 1e9;const int N = 1e5;const int REQ_ARMS = 5;const int REQ_LONGEST_ARM = 3;vi g[N];bool visited[N];int longest_down[N];void dfs_longest_down(int v, int p) {    assert(visited[v] == 0);    visited[v] = 1;    longest_down[v] = 0;    for(int u : g[v]) {        if (u == p) continue;        dfs_longest_down(u, v);        REMAX(longest_down[v], 1 + longest_down[u]);    }}int res = -1;int center_vertex = INF;void dfs(int v, int p, int up) {    int arms = 0;        int longest_arm = 0;    int longest_arm_vertex = -1;    int second_longest_arm = 0;    if (up > 0) {        arms = 1;        longest_arm = up;        longest_arm_vertex = p;    }    for(int u : g[v]) {        if (u == p) continue;        arms++;        int tmp = 1 + longest_down[u];        if (tmp > longest_arm) {            second_longest_arm = longest_arm;            longest_arm = tmp;            longest_arm_vertex = u;        } else if (tmp > second_longest_arm) {            second_longest_arm = tmp;        }    }    if (arms >= REQ_ARMS && longest_arm >= REQ_LONGEST_ARM) {        int sz = 1 + arms - 1 + longest_arm;        if (sz > res || (sz == res && v < center_vertex)) {            res = sz;            center_vertex = v;        }    }    for(int u : g[v]) {        if (u == p) continue;        int new_up = (u != longest_arm_vertex) ? 1 + longest_arm : 1 + second_longest_arm;        dfs(u, v, new_up);    }}int main()    {    ios_base::sync_with_stdio(0);    int n;    cin >> n;    assert(n >= 1 && n <= N);    FOR(i, n-1) {        int v, u;        cin >> v >> u;        assert(v >= 1 && v <= n);        assert(u >= 1 && u <= n);        assert(v != u);        --v, --u;        g[v].pb(u);        g[u].pb(v);    }    dfs_longest_down(0, -1);    FOR(i, n) assert(visited[i]);    dfs(0, -1, 0);    if (res == -1) {        cout << -1 << endl;    } else {        cout << res << " " << center_vertex+1 << endl;    }    return 0;}`

Second solution

`#include <bits/stdc++.h>using namespace std;const int LGN = 18;const int MAXN = 100005;int farthest, par[MAXN][LGN], depth[MAXN];vector <int> G[MAXN];void dfs(int pos, int prev){  depth[pos] = 1 + depth[prev];  par[pos][0] = prev;  if(depth[pos] > depth[farthest])    farthest = pos;  for (int i = 0; i < G[pos].size(); ++i)  {    if(G[pos][i] != prev)      dfs(G[pos][i],pos);  }}int lca(int u, int v){  if(depth[u] < depth[v])    return lca(v,u);  int diff = depth[u] - depth[v];  for (int i = 0; i < LGN; ++i)  {    if(diff & (1<<i))      u = par[u][i];  }  if(u == v)    return u;  for (int i = LGN - 1; i >= 0; --i)  {    if(par[u][i] != par[v][i])    {      u = par[u][i];      v = par[v][i];    }  }  return par[u][0];}int get_dist(int u, int v){  int l = lca(u,v);  return (depth[u] + depth[v] - 2*depth[l]);}int main(){  int n;  cin>>n;  for (int i = 0; i < n - 1; ++i)  {    int u,v;    cin>>u>>v;    G[u].push_back(v);    G[v].push_back(u);  }  farthest = 0;  dfs(1,0);  int dia1 = farthest;  farthest = 0;  dfs(dia1,0);  int dia2 = farthest;  for (int j = 1; j < LGN; ++j)  {    for (int i = 1; i <= n; ++i)    {      par[i][j] = par[par[i][j-1]][j-1];    }  }  int ansval = -1, ans = -1;  for (int i = 1; i <= n; ++i)  {    if(G[i].size() < 5)      continue;    int d = max(get_dist(i,dia1), get_dist(i,dia2));    if(d < 3)      continue;    if(d + (int)G[i].size() > ansval)    {      ansval = d + (int)G[i].size();      ans = i;    }  }  if(ansval == -1)    cout<<ansval<<"\n";  else    cout<<ansval<<" "<<ans<<"\n";  return 0;}`