oj.uz

Submission #918333

# Submission time Handle Problem Language Result Execution time Memory
918333 2024-01-29T16:54:48 Z contest_alt Friend (IOI14_friend) C++17
0 / 100
 4 ms 1372 KB 
#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[] ) {
    return 0;
  }

  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] = true;

      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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -