# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1186806 | astoria | Game (IOI14_game) | C11 | 0 ms | 0 KiB |
//trying to see if this can be done with o3
//note i've already solved this problem.
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
static const int MAXN = 1500 + 5;
static int parent_[MAXN], sz_[MAXN];
static int components, n;
static long long remaining;
static int maxSize;
static int Find(int v)
{
return parent_[v] == v ? v : parent_[v] = Find(parent_[v]);
}
static void Unite(int a, int b)
{
a = Find(a); b = Find(b);
if (a == b) return;
if (sz_[a] < sz_[b]) swap(a, b);
parent_[b] = a;
sz_[a] += sz_[b];
--components;
maxSize = max(maxSize, sz_[a]);
}
/* mandatory functions for the grader */
extern "C" {
void initialize(int N)
{
n = N;
for (int i = 0; i < n; ++i) parent_[i] = i, sz_[i] = 1;
components = n;
remaining = 1LL * n * (n - 1) / 2; // total number of questions
maxSize = 1;
}
int hasEdge(int u, int v)
{
--remaining; // after we see the question
if (Find(u) == Find(v)) // inside one component: always "NO"
return 0;
bool mustMerge = (components - 2) > remaining; // (1)
int newMax = max(maxSize, sz_[Find(u)] + sz_[Find(v)]);
bool safeMerge = 1LL * newMax * (n - newMax) > remaining; // (2)
if (mustMerge && safeMerge)
{
Unite(u, v);
return 1; // "YES"
}
else
{
return 0; // "NO"
}
}
} // extern "C"