제출 #773852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
773852		boris_mihov	게임 (IOI14_game)	C++17	42 / 100	1071 ms	5404 KiB

game

#include "game.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
#include <bitset>

typedef long long llong;
const int MAXN = 5000 + 10;

int n;
struct DSU
{
    int par[MAXN];
    int dep[MAXN];
    std::bitset <MAXN> isPresent[MAXN];

    void build()
    {
        std::iota(par + 1, par + 1 + n, 1);
        std::fill(dep + 1, dep + 1 + n, 1);
        for (int i = 1 ; i <= n ; ++i)
        {
            isPresent[i].set();
        }
    }

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

        return par[node] = find(par[node]);
    }

    void connect(int u, int v)
    {
        u = find(u);
        v = find(v);
        if (dep[u] < dep[v])
        {
            std::swap(u, v);
        }

        if (dep[u] == dep[v])
        {
            dep[v]++;
        }

        par[u] = v;
        for (int i = 1 ; i <= n ; ++i)
        {
            if (isPresent[u][i])
            {
                isPresent[i][u] = 0;
                isPresent[i][v] = 1;
            }
        }

        for (int i = 1 ; i <= n ; ++i)
        {
            if (isPresent[u][i])
            {
                isPresent[v][i] = 1;
            }
        }

        isPresent[v][u] = 0;
    }
};

DSU dsu;
std::bitset <MAXN> vis;

bool dfs(int node, int v)
{
    if (node == v || dsu.isPresent[node][v])
    {
        return true;
    }

    vis[node] = true;
    std::bitset <MAXN> bs = dsu.isPresent[node] ^ (dsu.isPresent[node] & vis);
    while (bs.count() > 0)
    {
        int first = bs._Find_first();
        if (!vis[first])
        {
            if (dfs(first, v))
            {
                return true;
            }

            bs ^= (bs & vis);
        }
    }

    return false;
}

void initialize(int N) 
{
    n = N;
    dsu.build();
}

int hasEdge(int u, int v) 
{
    u++; v++;
    u = dsu.find(u);
    v = dsu.find(v);
    dsu.isPresent[u][v] = 0;
    dsu.isPresent[v][u] = 0;
    vis.reset();

    if (dfs(u, v))
    {
        return 0;
    }

    dsu.connect(u, v);
    return 1;
}

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