Submission #773914

#	Time	Username	Problem	Language	Result	Execution time	Memory
773914		boris_mihov	Game (IOI14_game)	C++17	Compilation error	0 ms	0 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;
int d[MAXN];
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);
        }
    }
 
    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;
        d[v] = 0;

        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);
                }
            }
        }
        
        for (int i = 1 ; i <= n ; ++i)
        {
            isPresent[v][i] |= isPresent[u][i];
            d[v] += isPresent[v][i];
        }
        
        d[v] -= isPresent[v][u];
        isPresent[v][u] = false;

        if (d[v] > 100)
        {
            g[v].clear();
        } else
        {
            g[v].clear();
            g[v].reserve(d[v]);
            for (int i = 1 ; i <= n ; ++i)
            {
                if (isPresent[v][i])
                {
                    g[v].push_back(i);
                }
            }
        }
    }
};
 
DSU dsu;
bool vis[MAXN];
 
bool dfs(int node, int v)
{
    if (node == v || dsu.isPresent[node][v])
    {
        return true;
    }
 
    vis[node] = true;
    if (g[node].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 : 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();
    for (int i = 1 ; i <= n ; ++i)
    {
        d[i] = n - 1;
    }
}
 
int cntRemoved = 0;
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;
    cntRemoved++;
    
    if (d[u] > 1 && d[v] > 1 && (cntRemoved < d[u] * d[v] || dfs(u, v)))
    {
        d[u]--;
        d[v]--;
        return 0;
    }
    
    cntRemoved--;
    dsu.connect(u, v);
    return 1;
}

Compilation message (stderr)

game.cpp: In function 'bool dfs(int, int)':
game.cpp:108:9: error: 'g' was not declared in this scope
  108 |     if (g[node].empty())
      |         ^