Submission #918335

#	Time	Username	Problem	Language	Result	Execution time	Memory
918335		contest_alt	Friend (IOI14_friend)	C++17	11 / 100	54 ms	65536 KiB

friend

#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 ) {
    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] ){
        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( 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 );
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31