Submission #1168029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168029		Seungni	Game (IOI14_game)	C++20	100 / 100	327 ms	21920 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 = 0; 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];
        cnt[b][i] = 0;
        cnt[i][b] = 0;
    }

    par[b] = a;

    return;
}

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

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

    if (u == v)
    {
        return 0;
    }

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

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