제출 #918340

#제출 시각아이디문제언어결과실행 시간메모리
918340contest_alt친구 (IOI14_friend)C++17
11 / 100
18 ms1628 KiB
#include "friend.h" #include <vector> #include <algorithm> #include <random> const int MAXN = 1000; namespace Solver { std::vector<int> adj[MAXN]; void push_edge( int a, int b ) { adj[a].push_back( b ); adj[b].push_back( a ); } void make_graph( int n, int host[], int protocol[] ) { for( int i = 1 ; i < n ; i++ ){ if( protocol[i] == 0 ) push_edge( i, host[i] ); else if( protocol[i] == 1 ){ for( int x : adj[host[i]] ) push_edge( x, i ); }else{ for( int x : adj[host[i]] ) push_edge( x, i ); push_edge( host[i], i ); } } } int brute_force( int n, int v[] ) { int ret = 0; for( int mask = (1 << n) ; mask-- ; ){ int sum = 0; int isin[10]; for( int i = 0 ; i < n ; i++ ){ isin[i] = !!(mask & (1 << i)); sum += isin[i] * v[i]; } bool bad = false; for( int i = 0 ; i < n ; i++ ) for( int j : adj[i] ) bad |= (isin[i] & isin[j]); if( !bad ) ret = sum > ret ? sum : ret; } return ret; } const int NIL = -1; int pair[MAXN]; bool viz[MAXN]; bool try_pair( int u ) { viz[u] = true; for( int v : adj[u] ) if( pair[v] == NIL ){ pair[v] = u; pair[u] = v; return true; } viz[u] = true; for( int v : adj[u] ) if( !viz[v] ){ viz[v] = true; if( try_pair( pair[v] ) ){ pair[v] = u; pair[u] = v; return true; } } return false; } int bipartite( int n ) { // no need for v std::mt19937 rng( 6969 ); for( int i = 0 ; i < n ; i++ ){ pair[i] = NIL; std::shuffle( adj[i].begin(), adj[i].end(), rng ); } bool added = true; while( added ){ added = false; for( int i = 0 ; i < n ; i++ ) viz[i] = false; for( int i = 0 ; i < n ; i++ ) if( !viz[i] & pair[i] == NIL ) added |= try_pair( i ); } int ans = 0; for( int i = 0 ; i < n ; i++ ) ans += (pair[i] != NIL); return ans >> 1; } }; // Find out best sample int findSample( int n, int confidence[], int host[], int protocol[] ) { if( n > 1000 ) return -1; Solver::make_graph( n, host, protocol ); if( n <= 10 ) return Solver::brute_force( n, confidence ); return Solver::bipartite( n ); }

컴파일 시 표준 에러 (stderr) 메시지

friend.cpp: In function 'int Solver::bipartite(int)':
friend.cpp:105:31: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  105 |         if( !viz[i] & pair[i] == NIL )
      |                       ~~~~~~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...