Submission #911292

#	Time	Username	Problem	Language	Result	Execution time	Memory
911292		contest_alt	Game (IOI14_game)	C++17	42 / 100	1078 ms	4700 KiB

game

#include "game.h"

#include <random>
#include <time.h>
#include <algorithm>

const int SIZ = 250;
const int MAXN = SIZ * SIZ;

bool viz[SIZ];

struct Component {
  int adj[SIZ][SIZ];

  int n;

  void init( int N ) {
    n = N;

    for( int i = 0 ; i < n ; i++ ){
      for( int j = 0 ; j < n ; j++ )
        adj[i][j] = 1;
      adj[i][i] = 0;
    }
  }

  void remove_edge( int u, int v ) { adj[u][v] = adj[v][u] = 0; }
  void insert_edge( int u, int v ) { adj[u][v] = adj[v][u] = 1; }

  void dfs( int u ) {
    viz[u] = true;

    for( int v = 0 ; v < n ; v++ )
      if( !viz[v] && adj[u][v] )
        dfs( v );
  }

  bool connected( int u, int v ) {
    for( int i = 0 ; i < n ; i++ )
      viz[i] = false;

    dfs( u );

    return viz[v];
  }
};

namespace Solver {
  Component local[SIZ];
  int csiz[SIZ];
  
  Component global;

  int comp[MAXN];
  int comp_idx[MAXN];

  int edge_tracker[SIZ][SIZ];

  int n;
  int ncomp;

  void init( int N ) {
    n = N;

    std::mt19937 rng( clock() );

    for( int i = 0 ; i < n ; i++ ){
      comp[i] = i / SIZ;
      comp_idx[i] = i % SIZ;
      csiz[comp[i]]++;
    }

    for( int i = 0 ; i + 1 < n ; i++ ){
      int j = i + rng() % (n - i);

      std::swap( comp[i], comp[j] );
      std::swap( comp_idx[i], comp_idx[j] );
    }

    ncomp = (n - 1) / SIZ + 1;
    for( int i = 0 ; i < ncomp ; i++ )
      local[i].init( csiz[i] );

    global.init( ncomp );

    for( int i = 0 ; i < ncomp ; i++ )
      for( int j = i + 1 ; j < ncomp ; j++ )
        edge_tracker[i][j] = edge_tracker[j][i] = csiz[i] * csiz[j];
  }

  bool query( int u, int v ) {
    // problema locala?
    if( comp[u] == comp[v] ) {
      int C = comp[u];
      int a = comp_idx[u], b = comp_idx[v];
      
      local[C].remove_edge( a, b );

      if( local[C].connected( a, b ) )
        return false;

      local[C].insert_edge( a, b );
      return true;
    }

    // problema globala
    int U = comp[u], V = comp[v];
    if( edge_tracker[U][V] > 1 ){
      edge_tracker[U][V]--;
      return false;
    }

    global.remove_edge( U, V );

    if( global.connected( U, V ) )
      return false;

    global.insert_edge( U, V );
    return true;
  }
}

void initialize( int n ) { Solver::init( n ); }

int hasEdge( int u, int v ) { return Solver::query( u, v ); }

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