제출 #911294

#제출 시각아이디문제언어결과실행 시간메모리
911294contest_alt게임 (IOI14_game)C++17
42 / 100
1030 ms3624 KiB
#include "game.h" #include <random> #include <time.h> #include <algorithm> const int SIZ = 200; 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 ); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...