Submission #773838

#	Time	Username	Problem	Language	Result	Execution time	Memory
773838		boris_mihov	Game (IOI14_game)	C++17	0 / 100	1 ms	360 KiB

game

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

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

int n;
struct DSU
{
    int par[MAXN];
    int dep[MAXN];
    bool isPresent[MAXN][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)
        {
            std::fill(isPresent[i] + 1, isPresent[i] + 1 + n, 1);
        }
    }

    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);
        assert(u != 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)
        {
            isPresent[v][i] |= isPresent[u][i];
        }

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

DSU dsu;
bool vis[MAXN];

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

    vis[node] = true;
    for (int u = 1 ; u <= n ; ++u)
    {
        if (vis[u] || !dsu.isPresent[node][u])
        {
            continue;
        }

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

    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);
    std::fill(vis + 1, vis + 1 + n, false);
    dsu.isPresent[u][v] = 0;
    dsu.isPresent[v][u] = 0;
    if (dfs(u, v))
    {
        return 0;
    }

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

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