Submission #763444

#	Time	Username	Problem	Language	Result	Execution time	Memory
763444		adrilen	Game (IOI14_game)	C++17	100 / 100	295 ms	16692 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 1.5e3;

bitset <maxn> guessed[maxn];

int group[maxn];
basic_string<int> groups[maxn];


void initialize(int n) {
    for (int i = 0; i < n; i++) {
        group[i] = i;
        groups[i].push_back(i);
    }
}

int hasEdge(int u, int v) {
    int a = group[u], b = group[v];

    guessed[u][v] = guessed[v][u] = true;

    for (const int &i : groups[a])
    {
        for (const int &y : groups[b])
        {
            if (!guessed[i][y]) 
            {
                // Do not make a change
                return 0;
            }
        }
    }

    // Connect the groups
    if (groups[a].size() < groups[b].size()) swap(a, b);

    groups[a].insert(groups[a].end(), groups[b].begin(), groups[b].end());
    for (const int &i : groups[b]) group[i] = a;
 
    return 1;
}

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