제출 #918346

#제출 시각아이디문제언어결과실행 시간메모리
918346contest_alt친구 (IOI14_friend)C++17
50 / 100
19 ms4444 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 n - (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 ); int freq[3] = { 0, 0, 0 }; int not1 = 0; for( int i = 0 ; i < n ; i++ ){ if( confidence[i] != 1 ) not1++; if( i > 0 ) freq[protocol[i]]++; } if( freq[1] == n - 1 ){ int ret = 0; for( int i = 0 ; i < n ; i++ ) ret += confidence[i]; return ret; } if( freq[2] == n - 1 ){ int ret = 0; for( int i = 0 ; i < n ; i++ ) ret = confidence[i] > ret ? confidence[i] : ret; return ret; } if( !not1 && freq[2] == 0 ) return Solver::bipartite( n ); }

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

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
  156 | }
      | ^
#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...