Submission #1300037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300037		Faggi	Game (IOI14_game)	C++20	42 / 100	1093 ms	13644 KiB

game

#include <bits/stdc++.h>
#define ll int
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pb push_back
#define fr first
#define se second
#define mp make_pair
using namespace std;

const int MAXN = 1501;

bool arb[MAXN][MAXN], vis[MAXN];
vector<ll> grafo[MAXN];
ll memo[MAXN][MAXN], N, visi;

vector<pair<ll, ll>> ars;

void arm(ll nod)
{
    vis[nod] = 1;
    visi++;
    for (auto i : grafo[nod])
    {
        if (!vis[i])
        {
            ars.pb({nod, i});
            arb[nod][i] = arb[i][nod] = 1;
            arm(i);
        }
    }
}
ll vivas;
void initialize(int n)
{
    srand(time(NULL));
    N = n;
    vivas = (N * (N - 1)) / 2;
    ll i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            if (i != j)
                grafo[i].pb(j);
            memo[i][j] = -1;
        }
    for (i = 0; i < n; i++)
        random_shuffle(all(grafo[i]));
    arm(rand() % n);
}
vector<pair<ll, ll>> ant;
bool isconex()
{
    memset(vis, 0, sizeof(vis));
    ant = ars;
    visi = 0;
    for (auto &k : ars)
        arb[k.fr][k.se] = arb[k.se][k.fr] = 0;
    ars.resize(0);
    arm(rand() % N);
    ll i;
    if (visi != N)
    {
        swap(ant, ars);
        for (auto k : ars)
            arb[k.fr][k.se] = arb[k.se][k.fr] = 1;
        return 0;
    }
    return 1;
}

void bor(ll u, ll v)
{
    vector<ll> vec;
    for (auto k : grafo[u])
        if (k != v)
            vec.pb(k);
    swap(vec, grafo[u]);
}

int hasEdge(int u, int v)
{
    if (vivas == N - 1)
        return 1;
    if (u == v)
        return 0;
    if (memo[u][v] != -1)
        return memo[u][v];
    bor(u, v);
    bor(v, u);
    if (!arb[u][v])
    {
        memo[u][v] = memo[v][u] = 0;
        vivas--;
        return 0;
    }
    if (isconex())
    {
        memo[u][v] = memo[v][u] = 0;
        vivas--;
        return 0;
    }
    grafo[u].pb(v);
    grafo[v].pb(u);
    memo[u][v] = memo[v][u] = 1;
    return 1;
}

Compilation message (stderr)

game.cpp: In function 'void initialize(int)':
game.cpp:48:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   48 |         random_shuffle(all(grafo[i]));
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from game.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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