OJ Board

Code: Select all

//
//  main.cpp
//  12083 - Guardian of Decency
//
//  Created by Repon Macbook on 6/25/15.
//  Copyright (c) 2015 Repon Macbook. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				505
#define ll				long long
#define ull				unsigned long long
#define mod				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define debug(x)              cout <<#x <<" -> " << x << endl;
#define EPS				1e-7
#define fred()                 freopen("in.txt","r",stdin);
#define fwrt()               freopen("in.txt","w",stdout);


/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

map<string, int> lm ;
map<string, int> sm;
vi EdgeList[LMT];

struct Person {
      int h , music , sport;
};

vector<Person> Male , Female;

char mus[103] , sp[103] ;

int S[LMT] , T[LMT] , P[LMT];

bool isLove ( int i , int j )
{
      
      if( abs(Male[i].h - Female[j].h ) <= 40 && Male[i].music == Female[j].music && Male[i].sport != Female[j].sport ) {
            return true;
      }
      return false;
}


bool dfs( int s)
{
      S[s] = 1;
      for( int i = 0; i < EdgeList[s].size() ; i ++ ) {
            int v = EdgeList[s][i] ;
            if( T[v] == 0 ){
                  T[v] = 1;
                  if( P[v] == -1 || dfs(v)) {
                        P[v] = s;
                        return true;
                  }
            }
      }
      return false;
}


int bmp ( int n)
{
      int r = 0;
      ms(P , -1);
      for( int i =0 ; i < n ;i ++ ) {
            ms(S, 0);
            ms(T , 0);
            if( dfs(i)) r ++;
      }
      return r;
}
int main()
{
      
      int tc , h ;
      int n ;
      sc(tc);
      
      char sx;
      while (tc-- ) {
            sc(n);
            int cn1 = 0, cn2 = 0;
            for (int i = 0; i < n ; i ++) {
                  scanf("%d %c %s %s" , &h , &sx , mus , sp);
                  
                  if( lm.count(mus) == 0) lm[mus] = ++cn1;
                  if( sm.count(sp) == 0 )sm[sp] = ++ cn2;
                  
                  
                  if( sx == 'M' )Male.push_back( {h,lm[mus] , sm[sp]} );
                  
                  else Female.push_back( {h,lm[mus] , sm[sp]} );
                  
            }
            
            for( int i =0 ; i < Male.size()  ; i ++ ) {
                  for( int j = 0; j < Female.size() ; j ++ ) {
                        if( isLove ( i , j )) {
                              EdgeList[i].pb( j );
                        }
                  }
            }
            
            int p = bmp ( (int ) Male.size()) ;
            
            printf("%d\n" , n - p );
            
            for( int i = 0 ;i  < Male.size() ;i ++) EdgeList[i].clear();
            Male.clear();
            Female.clear();
            lm.clear();
            sm.clear();
      }
      return 0;
}