Submission #1300031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300031		Faggi	Game (IOI14_game)	C++20	42 / 100	1096 ms	13444 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;

mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
bool arb[MAXN][MAXN], vis[MAXN];
vector<ll>grafo[MAXN];
ll memo[MAXN][MAXN], N;

vector<pair<ll,ll>>ars;

void arm(ll nod)
{
    vis[nod]=1;
    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(rng()%n);
}

bool isconex()
{
    memset(vis,0,sizeof(vis));
    vector<pair<ll,ll>>ant=ars;
    for(auto k:ars)
        arb[k.fr][k.se]=arb[k.se][k.fr]=0;
    ars.resize(0);
    arm(rng()%N);
    for(ll i=0; i<N; i++)
        if(!vis[i])
        {
            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:47: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]
   47 |         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