HackerEarth Beautiful Badges problem solution

In this HackerEarth Beautiful Badges Assignment problem solution Lucy has got the task to create badges for all students of the school. A badge is created by superimposing two squares. The bottom square should be of blue colour and top square should be of yellow colour. The squares must be rotated in such a way that the projection of the badge displays 8 distinguishable vertices.

Please help Lucy find out the maximum number of badges she can make with available n squares.

HackerEarth Beautiful Badges problem solution.

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

#define MOD                     1000000007
#define pb(x)                   push_back(x)
#define mp(x,y)                 make_pair(x,y)
#define FF                      first
#define SS                      second
#define s(n)                    scanf("%d",&n)
#define sl(n)                   scanf("%lld",&n)
#define sf(n)                   scanf("%lf",&n)
#define ss(n)                   scanf("%s",n)
#define sc(n)                   {char temp[4]; ss(temp); n=temp[0];}
#define LINF                    (long long)1e18
#define EPS                     1e-9
#define maX(a,b)                ((a)>(b)?(a):(b))
#define miN(a,b)                ((a)<(b)?(a):(b))
#define abS(x)                  ((x)<0?-(x):(x))

typedef long long ll;
typedef unsigned long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> TRI;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<ll> vl;
typedef vector<PII> VII;
typedef vector<TRI> VT;

int N, m;
PII a[100005];
const int MAXN = 2005;
int cnt[MAXN], one_st;


const int INF = 1000000000;
 

struct edge {
  int a, b, cap, flow;
};
 
int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
vector<int> g[MAXN];
 
void add_edge (int a, int b, int cap) {
  edge e1 = { a, b, cap, 0 };
  edge e2 = { b, a, 0, 0 };
  g[a].push_back ((int) e.size());
  e.push_back (e1);
  g[b].push_back ((int) e.size());
  e.push_back (e2);
}
 
bool bfs() {
  int qh=0, qt=0;
  q[qt++] = s;
  memset (d, -1, n * sizeof d[0]);
  d[s] = 0;
  while (qh < qt && d[t] == -1) {
    int v = q[qh++];
    for (size_t i=0; i<g[v].size(); ++i) {
      int id = g[v][i],
        to = e[id].b;
      if (d[to] == -1 && e[id].flow < e[id].cap) {
        q[qt++] = to;
        d[to] = d[v] + 1;
      }
    }
  }
  return d[t] != -1;
}
 
int dfs (int v, int flow) {
  if (!flow)  return 0;
  if (v == t)  return flow;
  for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
    int id = g[v][ptr[v]],
      to = e[id].b;
    if (d[to] != d[v] + 1)  continue;
    int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
    if (pushed) {
      e[id].flow += pushed;
      e[id^1].flow -= pushed;
      return pushed;
    }
  }
  return 0;
}
 
int dinic() {
  int flow = 0;
  for (;;) {
    if (!bfs())  break;
    memset (ptr, 0, n * sizeof ptr[0]);
    while (int pushed = dfs (s, INF))
      flow += pushed;
  }
  return flow;
}

void precompute() {
}
void read() {
  s(N);
  for (int i = 0; i < N; ++i) {
    int c_i, d_i;
    s(c_i), s(d_i);
    a[i] = make_pair(c_i, d_i);
  }
}
void preprocess() {
  sort(a, a + N);
  int cur = -1;
  one_st = -1;
  for (int i = 0; i < N; ++i) {
    if(i == 0 or (a[i] != a[i - 1])) {
      ++cur;
      cnt[cur] = 1;
    }
    else cnt[cur]++;
    if(one_st == -1 and a[i].FF == 2) one_st = cur;
  }
  N = unique(a, a + N) - a;
}

void solve() {
  n = N + 2;;
  s = 0, t = N + 1;
  for (int i = 0; i < N; ++i) {
    if(i < one_st) add_edge(s, i + 1, cnt[i]);
    else add_edge(i + 1, t, cnt[i]);
  } 
  for (int i = 0; i < one_st; ++i) {
    int mind = ceil(a[i].SS / sqrt(2.0));
    int maxd = floor(a[i].SS * sqrt(2.0));
    for (int j = one_st; j < N; ++j) {
      assert(a[j].FF != a[i].FF);
      if(a[j].SS <= maxd and a[j].SS >= mind) 
        add_edge(i + 1, j + 1, min(cnt[i], cnt[j])); 
    }     
  }
  cout << dinic();
}
int main() {
    precompute();
    read();
    preprocess();
    solve();
    return 0;
}