Submission #773880

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

game

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

typedef long long llong;
const int MAXN = 5000 + 10;
 
int n;
struct DSU
{
    int par[MAXN];
    int dep[MAXN];
    bool isPresent[MAXN][MAXN];
    std::vector <int> g[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);
            isPresent[i][i] = false;
        }
    }
 
    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;
                if (g[i].size())
                {
                    g[i].push_back(v);
                }
            }
        }
        
        int cntOnes = 0;
        for (int i = 1 ; i <= n ; ++i)
        {
            isPresent[v][i] |= isPresent[u][i];
            cntOnes += (isPresent[v][i]);
        }
 
        isPresent[v][u] = false;
        if (cntOnes <= sqrt(n))
        {
            g[v].clear();
            g[v].reserve(cntOnes);
            for (int i = 1 ; i <= n ; ++i)
            {
                if (isPresent[v][i])
                {
                    g[v].push_back(i);
                }
            }
        } else
        {
            g[v].clear();
        }
    }
};
 
DSU dsu;
bool vis[MAXN];
 
bool dfs(int node, int v)
{
    if (node == v || dsu.isPresent[node][v])
    {
        return true;
    }
 
    vis[node] = true;
    if (dsu.g[v].empty())
    {
        for (int u = 1 ; u <= n ; ++u)
        {
            if (vis[u] || !dsu.isPresent[node][u])
            {
                continue;
            }
    
            if (dfs(u, v))
            {
                return true;
            }
        }
    } else
    {
        for (const int &u : dsu.g[node])
        {
            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] = false;
    dsu.isPresent[v][u] = false;
 
    if (dfs(u, v))
    {
        return 0;
    }
 
    dsu.connect(u, v);
    return 1;
}

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