Submission #1186834

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

game

/*
   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;
}

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