제출 #588219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588219		AlperenT	게임 (IOI14_game)	C++17	0 / 100	1 ms	308 KiB

game

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

using namespace std;

const int N = 1500 + 5;

struct DSU{
    int par[N], setsize[N], cursize[N];

    void init(int n){
        for(int i = 0; i < n; i++) par[i] = i, setsize[i] = i, cursize[i] = n - 1;
    }

    int setfind(int a){
        if(a == par[a]) return a;
        else return par[a] = setfind(par[a]);
    }

    void setunion(int a, int b){
        a = setfind(a), b = setfind(b);

        if(a != b){
            if(setsize[b] > setsize[a]) swap(a, b);
            par[b] = par[a];
            setsize[a] += setsize[b];
            cursize[a] += cursize[b];
        }
    }
};

DSU dsu;

void initialize(int n) {
    dsu.init(n);
}

int hasEdge(int u, int v) {
    dsu.cursize[dsu.setfind(u)]--;
    dsu.cursize[dsu.setfind(v)]--;

    if(dsu.cursize[dsu.setfind(u)] == 0 || dsu.cursize[dsu.setfind(v)] == 0){
        dsu.setunion(u, v);
        return true;
    }
    else return false;
}

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