Submission #1231432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231432		LucaIlie	Game (IOI14_game)	C++20	42 / 100	1095 ms	1172 KiB

game

#include "game.h"
#include <vector>

using namespace std;

const int MAX_N = 1500;
int n;
bool ap[MAX_N][MAX_N];
vector<pair<int, int>> edges;

struct DSU {
    int comp;
    vector<int> parent;

    void init(int n) {
        parent.clear();
        parent.resize(n);
        for (int v = 0; v < n; v++)
            parent[v] = v;
        comp = n;
    }

    int findParent(int v) {
        if (parent[v] != v)
            parent[v] = findParent(parent[v]);
        return parent[v];
    }

    void connect(int u, int v) {
        u = findParent(u);
        v = findParent(v);
        if (u == v)
            return;
        comp--;
        parent[u] = v;
    }
};

void initialize(int N) {
    n = N;
    edges.clear();
    for (int u = 0; u < n; u++) {
        for (int v = u + 1; v < n; v++)
            ap[u][v] = false;
    }
}

int hasEdge(int u, int v) {
    ap[u][v] = ap[v][u] = true;
    DSU dsu;
    dsu.init(n);

    for (auto e: edges)
        dsu.connect(e.first, e.second);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (ap[i][j])
                continue;
            dsu.connect(i, j);
        }
    }

    if (dsu.comp == 1)
        return 0;
    edges.push_back({u, v});
    return 1;
}

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