Submission #1137291

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

game

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

using namespace std;

struct DSU {
    int n;
    vector<int> p;
    vector<vector<int>> st;

    void xxx(int n) {
        this->n = n;
        p.resize(n);
        st.resize(n);

        for (int i = 0; i < n; ++i) {
            p[i] = i;
            st[i].push_back(i);
        }
    }

    int find_set(int v) {
        return v == p[v] ? v : p[v] = find_set(p[v]);
    }

    void unite(int u, int v) {
        u = find_set(u);
        v = find_set(v);

        if (u == v) return;

        if (st[u].size() > st[v].size()) swap(u, v);

        p[u] = v;

        for (auto i : st[u]) {
            st[v].push_back(i);
        }
        st[u].clear();
    }
};

DSU g;
bool used[1500][1500];

void initialize(int n) {
    g.xxx(n);
}

int hasEdge(int U, int V) {
    int u = g.find_set(U);
    int v = g.find_set(V);

    if (u == v) return 0;

    bool flag = true;

    for (auto a : g.st[u]) {
        for (auto b : g.st[v]) {
            if (!used[a][b]) {
                flag = false;
                break;
            }
        }
    }

    used[U][V] = used[V][U] = true;

    if (flag) {
        g.unite(u, v);
        return 1;
    } else return 0;
}

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