Submission #136773

#	Time	Username	Problem	Language	Result	Execution time	Memory
136773		mlyean00	Game (IOI14_game)	C++14	100 / 100	506 ms	25304 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

struct disjoint_set {
    int n;
    vector<int> parent;
    vector<list<int>> elem;
    vector<vector<int>> maybe_cnt;

    disjoint_set() {}

    disjoint_set(int n)
        : n(n), parent(n), elem(n), maybe_cnt(n, vector<int>(n, 1)) {
        iota(parent.begin(), parent.end(), 0);
        for (int i = 0; i < n; ++i) {
            maybe_cnt[i][i] = 0;
            elem[i].push_back(i);
        }
    }

    bool query(int u, int v) {
        u = parent[u];
        v = parent[v];
        if (maybe_cnt[u][v] == 1) {
            for (int i : elem[v]) {
                parent[i] = u;
            }
            elem[u].splice(elem[u].end(), elem[v]);
            for (int x = 0; x < n; ++x) {
                if (parent[x] != x) continue;
                maybe_cnt[u][x] += maybe_cnt[v][x];
                maybe_cnt[x][u] += maybe_cnt[x][v];
            }
            return true;
        } else {
            --maybe_cnt[u][v];
            --maybe_cnt[v][u];
            return false;
        }
    }
};

disjoint_set ds;

void initialize(int n) {
    ds = disjoint_set(n);
}

int hasEdge(int u, int v) {
    return ds.query(u, v);
}

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