Submission #1186812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186812		astoria	Game (IOI14_game)	C++20	0 / 100	0 ms	324 KiB

game

#include "game.h"            // <<<  organiser’s header
#include "bits/stdc++.h"

using namespace std;

static const int MAXN = 1500 + 5;
static int parent_[MAXN], sz_[MAXN];
static int components, n, maxSize;
static long long remaining;

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]);
}

/*  The header already has `extern "C"` when compiled as C++,  
    so we just write the definitions.                       */
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;
    maxSize=1;
}

int hasEdge(int u,int v)
{
    --remaining;

    if(Find(u)==Find(v)) return 0;               // inside one component

    bool mustMerge = (components-2) > remaining;            // condition (1)
    int  newMax    = max(maxSize, sz_[Find(u)] + sz_[Find(v)]);
    bool safeMerge = 1LL*newMax*(n-newMax) > remaining;     // condition (2)

    if(mustMerge && safeMerge){
        Unite(u,v);
        return 1;
    }
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 27
• Subtask 3: 0 / 58