Submission #773927

#	Time	Username	Problem	Language	Result	Execution time	Memory
773927		boris_mihov	Game (IOI14_game)	C++17	100 / 100	371 ms	23812 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];
 
    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;
            }
        }
        
        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;
    }
};
 
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();
    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++;
    
    int cntOne = 0;
    int cntTwo = 0;

    for (int i = 1 ; i <= n ; ++i)
    {
        if (dsu.isPresent[u][i] && dsu.isPresent[v][i])
        {
            d[u]--;
            d[v]--;
            return 0;
        }

        cntOne += dsu.isPresent[u][i] - 1;
        cntTwo += dsu.isPresent[v][i] - 1;
    }

    if (cntOne * cntTwo / 4 > cntRemoved)
    {
        d[u]--;
        d[v]--;
        return 0;
    }
    
    if (d[u] > 1 && d[v] > 1 && cntRemoved < d[u] * d[v])
    {
        d[u]--;
        d[v]--;
        return 0;
    }
    
    cntRemoved--;
    dsu.connect(u, v);
    return 1;
}

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