oj.uz

Submission #918343

# Submission time Handle Problem Language Result Execution time Memory
918343 2024-01-29T17:09:57 Z contest_alt Friend (IOI14_friend) C++17
34 / 100
 18 ms 1496 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[] ) {
    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 );

  return Solver::bipartite( n );
}

Compilation message

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 )
      |                       ~~~~~~~~^~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

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 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 460 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 18 ms 1496 KB Output isn't correct
13 Halted 0 ms 0 KB -