/*
IOI 2014 – Game
Always keep the "possible‑edge graph" connected:
If a question is the last unanswered pair between two components,
answer YES and merge; otherwise answer NO.
*/
#include "game.h" // provided by the organisers
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1500 + 5;
/* ---------- disjoint‑set union ---------- */
static int parent_[MAXN], sz_[MAXN];
static int Find(int v) // path compression
{
return parent_[v] == v ? v : parent_[v] = Find(parent_[v]);
}
static int Unite(int a, int b) // union by size, returns new root
{
a = Find(a); b = Find(b);
if (a == b) return a;
if (sz_[a] < sz_[b]) swap(a, b);
parent_[b] = a;
sz_[a] += sz_[b];
return a;
}
/* ---------- matrix of remaining pairs between components ---------- */
static uint16_t rem_[MAXN][MAXN]; // symmetrical, 0 on diagonal
static int n; // number of cities
/* ---------- mandatory functions ---------- */
void initialize(int N)
{
n = N;
for (int i = 0; i < n; ++i) {
parent_[i] = i;
sz_[i] = 1;
for (int j = 0; j < n; ++j) rem_[i][j] = 0;
}
/* a single unanswered pair between every two distinct cities */
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
rem_[i][j] = rem_[j][i] = 1;
}
int hasEdge(int u, int v)
{
int a = Find(u), b = Find(v);
if (a == b) // inside one component → always NO
return 0;
/* this question removes one unanswered pair between a and b */
if (--rem_[a][b], --rem_[b][a], rem_[a][b] == 0) {
/* last possible pair → answer YES and merge the components */
int newRoot = Unite(a, b); // merge b into a (or vice versa)
/* add row/column 'b' into 'a' (now 'newRoot') */
for (int x = 0; x < n; ++x) if (x != newRoot) {
int r1 = rem_[newRoot][x] + rem_[b][x];
rem_[newRoot][x] = rem_[x][newRoot] = r1;
}
return 1; // "YES"
}
/* there are still unanswered pairs between a and b → safe to say NO */
return 0;
}
