Submission #66847

#	Time	Username	Problem	Language	Result	Execution time	Memory
66847		Kubalionzzale	Game (IOI14_game)	C++14	100 / 100	727 ms	159164 KiB

game

#include "game.h"

#include <iostream>
#include <algorithm>
#include <set>

int cnt[1510] = { 0 };
int g[1510][1510] = { 0 };
//1 - not connected
//0 - connected
int n;
bool treed[1510] = { 0 };

void initialize(int N) {
    n = N;
    for (int i = 0; i < n; ++i)
    {
        cnt[i] = 1;
    }

    treed[0] = true;
}

int hasEdge(int u, int v) {

    if (treed[u] && treed[v])
    {
        g[u][v] = 1;
        g[v][u] = 1;
        return 0;
    }

    if (!treed[u] && !treed[v])
    {
        g[u][v] = 1;
        g[v][u] = 1;
        return 0;
    }

    if (treed[u])
    {
        if (cnt[v] == 1)
        {
            for (int i = 0; i < n; ++i)
            {
                if (!g[i][v])
                {
                    g[i][v] = 1;
                    ++cnt[i];
                }
            }
            treed[v] = true;

            return 1;
        }
        else
        {
            g[u][v] = 1;
            g[v][u] = 1;

            --cnt[v];
            return 0;
        }
    }
    else if (treed[v])
    {
        if (cnt[u] == 1)
        {
            for (int i = 0; i < n; ++i)
            {
                if (!g[i][u])
                {
                    g[i][u] = 1;
                    ++cnt[i];
                }
            }

            treed[u] = true;
            return 1;
        }
        else
        {
            g[u][v] = 1;
            g[v][u] = 1;

            --cnt[u];
            return 0;
        }
    }
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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