Submission #773791

#	Time	Username	Problem	Language	Result	Execution time	Memory
773791		boris_mihov	Game (IOI14_game)	C++17	42 / 100	1087 ms	2688 KiB

game

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

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

int n;
bool isPresent[MAXN][MAXN];
bool vis[MAXN];

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

        sz += dfs(u);
    }

    return sz;
}

void initialize(int N) 
{
    n = N;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::fill(isPresent[i] + 1, isPresent[i] + 1 + n, true);
        vis[i] = false;
    }
}

int hasEdge(int u, int v) 
{
    u++; v++;
    std::fill(vis + 1, vis + 1 + n, false);
    isPresent[u][v] = 0;
    isPresent[v][u] = 0;
    if (dfs(1) == n)
    {
        return 0;
    }

    isPresent[u][v] = 1;
    isPresent[v][u] = 1;
    return 1;
}

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