oj.uz

Submission #918349

# Submission time Handle Problem Language Result Execution time Memory
918349 2024-01-29T17:16:40 Z contest_alt Friend (IOI14_friend) C++17
69 / 100
 18 ms 4444 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);
  }

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 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 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 4 ms 4188 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 3164 KB Output is correct
5 Correct 4 ms 4188 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 5 ms 4444 KB Output is correct

Subtask #4
19.0 / 19.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 456 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 468 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 368 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #5
23.0 / 23.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 1 ms 532 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 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 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 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 1 ms 344 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 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Incorrect 18 ms 1628 KB Output isn't correct
13 Halted 0 ms 0 KB -