제출 #1168025

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

game

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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N;
int par[3005];
int cnt[3005][3005];

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

void merge(int a, int b)
{
    a = find(a), b = find(b);
    if (a == b) return;

    cnt[a][b] = 0, cnt[b][a] = 0;

    set <int> v;
    for (int i = 1; i <= N; i++)
    {
        int t = find(i);
        v.insert(t);
    }

    v.erase(a);
    v.erase(b);

    for (int i : v)
    {
        cnt[a][i] += cnt[b][i];
        cnt[i][a] += cnt[b][i];
    }

    par[b] = a;

    return;
}

void initialize(int n)
{
    for (int i = 1; i <= n; i++) par[i] = i;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++) cnt[i][j] = 1;
    }
}

int hasEdge(int u, int v)
{
    u = find(u), v = find(v);

    if (cnt[u][v] == 1)
    {
        merge(u, v);
        return 1;
    }
    else
    {
        cnt[u][v]--;
        cnt[v][u]--;
        return 0;
    }
}

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