Submission #700426

#	Time	Username	Problem	Language	Result	Execution time	Memory
700426		Cyanmond	Game (IOI14_game)	C++17	100 / 100	562 ms	25228 KiB

game

#include "game.h"
#include <bits/stdc++.h>

struct UnionFind {
    int n;
    std::vector<int> data;
    std::vector<std::vector<int>> edges;

    UnionFind(int n_) : n(n_) {
        edges.resize(n, std::vector<int>(n, 1));
        data.assign(n, -1);
    }

    int find(int v) {
        if (data[v] < 0) {
            return v;
        } else {
            return data[v] = find(data[v]);
        }
    }

    int groupSize(int v) {
        return -data[find(v)];
    }

    bool merge(int a, int b) {
        a = find(a);
        b = find(b);
        assert(edges[a][b] == edges[b][a]);
        --edges[a][b];
        --edges[b][a];
        if (a == b) {
            return false;
        }
        if (edges[a][b] != 0) {
            return false;
        }

        if (groupSize(a) < groupSize(b)) {
            std::swap(a, b);
        }
        data[a] += data[b];
        data[b] = a;

        // edge
        for (int i = 0; i < n; ++i) {
            if (find(i) != i) {
                continue;
            }
            if (i == a or i == b) {
                continue;
            }
            edges[a][i] += edges[b][i];
            edges[i][a] += edges[i][b];
        }
        return true;
    }
};

UnionFind uft(0);
void initialize(int n) {
    uft = UnionFind(n);
}

int hasEdge(int u, int v) {
    return uft.merge(u, v);
}

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