Submission #918349

#	Time	Username	Problem	Language	Result	Execution time	Memory
918349		contest_alt	Friend (IOI14_friend)	C++17	69 / 100	18 ms	4444 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 ) {
    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);
  }

  int dp[MAXN][2];
  int *vals;

  void calc_dp( int u, int p ) {
    dp[u][false] = 0;
    dp[u][true] = vals[u];

    for( int v : adj[u] )
      if( v != p ){
        calc_dp( v, u );

        dp[u][false] += std::max( dp[v][true], dp[v][false] );
        dp[u][true] += dp[v][false];
      }
  }

  int tree( int n, int *_v ) {
    vals = _v;
    calc_dp( 0, 0 );

    return std::max( dp[0][true], dp[0][false] );
  }
};

// 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 );

  return Solver::tree( n, confidence );
}

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