제출 #1137292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137292		viwlesxq	Game (IOI14_game)	C++20	100 / 100	362 ms	9212 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;

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

    bool flag = false;

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

    if (flag) return 0;
    
    g.unite(U, V);
    return 1;
}

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