Submission #66845

#	Time	Username	Problem	Language	Result	Execution time	Memory
66845		Kubalionzzale	Game (IOI14_game)	C++14	42 / 100	1076 ms	4372 KiB

game

#include "game.h"

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

std::vector< std::vector<int> > g(1510);

int cnt[1510] = { 0 }, cnting = 0;
int curi, curj;
int n;
bool visited[1510] = { 0 };

void dfs(int index)
{
    ++cnting;
    visited[index] = true;
    for (int i = 0; i < g[index].size(); ++i)
    {
        int next = g[index][i];

        if ((curi == index && curj == next) || (curi == next && curj == index))
        {
            continue;
        }

        if (!visited[next])
            dfs(next);
    }


}

void dfss(int index)
{
    for (int i = 0; i < n; ++i)
    {
        visited[i] = 0;
    }
    cnting = 0;
    dfs(0);
}

void initialize(int N) {
    n = N;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            g[i].push_back(j);
            g[j].push_back(i);
        }
    }
}

int hasEdge(int u, int v) {
    curi = u;
    curj = v;
    dfss(0);

    if (cnting == n)
    {
        for (int i = 0; i < g[u].size(); ++i)
        {
            if (g[u][i] == v)
            {
                g[u].erase(g[u].begin() + i);
                break;
            }
        }

        for (int i = 0; i < g[v].size(); ++i)
        {
            if (g[v][i] == u)
            {
                g[v].erase(g[v].begin() + i);
                break;
            }
        }

        return 0;
    }
    else
    {
        return 1;
    }
}

Compilation message (stderr)

game.cpp: In function 'void dfs(int)':
game.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[index].size(); ++i)
                     ~~^~~~~~~~~~~~~~~~~
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[u].size(); ++i)
                         ~~^~~~~~~~~~~~~
game.cpp:73:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); ++i)
                         ~~^~~~~~~~~~~~~

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