제출 #1003221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003221		coolboy19521	게임 (IOI14_game)	C++17	100 / 100	271 ms	25540 KiB

game

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

using namespace std;

const int sz = 1550;

int as[sz][sz];
int N;

struct DSU {
    vector<int> par;
    DSU(int n) {
        par.assign(n, -1);
    }
    int Find(int v) {
        if (0 > par[v]) return v;
        return par[v] = Find(par[v]);
    }
    void Unite(int v, int u) {
        v = Find(v);
        u = Find(u);
        if (par[v] > par[u]) {
            swap(v, u);
        }
        par[v] += par[u];
        for (int i = 0; i < N; i ++) {
            as[v][i] += as[u][i];
            as[i][v] += as[i][u];
        }
        par[u] = v;
    }
};

DSU* dsu;

void initialize(int n) {
    N = n;
    dsu = new DSU(n);
}

int hasEdge(int u, int v) {
    u = dsu->Find(u);
    v = dsu->Find(v);
    int n = -dsu->par[u];
    int m = -dsu->par[v];

    if (n < m) {
        swap(u, v);
    }

    if (as[u][v] == n * m - 1) {
        as[u][v] ++;
        as[v][u] = as[u][v];
        dsu->Unite(u, v);
        return 1;
    } else {
        as[u][v] ++;
        as[v][u] = as[u][v];
    }

    return 0;
}

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