Submission #1062627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062627		damjandavkov	Game (IOI14_game)	C++17	42 / 100	1095 ms	4696 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > v;
vector<int> pa;
vector<vector<bool> > w;
vector<bool> wh;
int N;
int dfs(int i)
{
    int s = 1;
    random_shuffle(v[i].begin(), v[i].end());
    for (auto h : v[i])
    {
        if (!wh[h] && w[i][h])
        {
            pa[h] = i;
            wh[h] = 1;
            s += dfs(h);
        }
    }
    return s;
}
void initialize(int n)
{
    int i, j;
    N = n;
    v.resize(n);
    pa.resize(n);
    w.resize(n);
    wh.resize(n);
    for (i = 0; i < n; i++)
    {
        w[i].resize(n);
        for (j = 0; j < n; j++)
        {
            if (j == i)
                w[i][j] = 0;
            else
            {
                w[i][j] = 1;
                v[i].push_back(j);
            }
        }
    }
    for (i = 0; i < n; i++)
        wh[i] = 0;
    wh[0] = 1;
    pa[0] = 0;
    dfs(0);
}
int hasEdge(int u, int v)
{
    w[u][v] = w[v][u] = 0;
    if (pa[u] != v && pa[v] != u)
        return 0;
    int s = 0;
    s = rand() % N;
    for (int i = 0; i < N; i++)
        wh[i] = 0;
    wh[s] = 1;
    pa[s] = s;
    if (dfs(s) == N)
        return 0;
    w[u][v] = w[v][u] = 1;
    return 1;
}

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