学步园

传送门：【HDU】2860 Regroup

题目分析：其实就是披着并查集外表的模拟题，照着做就好了。。。话说题目中给了x==y。。这个真的大丈夫？。。

代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )

typedef long long LL ;

const int MAXN =     100005 ;
const LL INF  = 1e11 ;

int p[MAXN] ;
LL rate[MAXN] ;
int n , m , k ;
char s[5] ;

int find ( int x ) {
	int ans , tmp , o = x ;
	while ( p[o] != o )
		o = p[o] ;
	ans = o ;
	o = x ;
	while ( p[o] != o ) {
		tmp = p[o] ;
		p[o] = ans ;
		o = tmp ;
	}
	return ans ;
}

void read ( int &x ) {
	x = 0 ;
	char c = ' ' ;
	while ( c < '0' || c > '9' )
		c = getchar () ;
	while ( c >= '0' && c <= '9' ) {
		x = x * 10 + c - '0' ;
		c = getchar () ;
	}
}

void work () {
	int newbie , c ;
	int x , y ;
	REP ( i , n )
		p[i] = i , rate[i] = INF ;
	input () ;
	REP ( i , m ) {
		scanf ( "%s" , s ) ;
		if ( s[0] == 'A' ) {
			scanf ( "%d%d" , &newbie , &c ) ;
			if ( c != find ( c ) )
				printf ( "Reject\n" ) ;
			else {
				printf ( "Accept\n" ) ;
				if ( rate[c] > newbie )
					rate[c] = newbie ;
			}
		}
		if ( s[0] == 'G' ) {
			scanf ( "%d" , &c ) ;
			x = find ( c ) ;
			if ( x != c )
				printf ( "Company %d is a part of company %d.\n" , c , x ) ;
			else if ( rate[c] == INF )
				printf ( "Company %d is empty.\n" , c ) ;
			else
				printf ( "Lowest rate: %I64d.\n" , rate[c] ) ;
		}
		if ( s[0] == 'M' ) {
			scanf ( "%d%d" , &x , &y ) ;
			if ( x != find ( x ) || y != find ( y ) || x == y )
				printf ( "Reject\n" ) ;
			else {
				printf ( "Accept\n" ) ;
				p[y] = x ;
				if ( rate[x] > rate[y] )
					rate[x] = rate[y] ;
			}
		}
	}
	printf ( "\n" ) ;
}

int main () {
	while ( ~scanf ( "%d%d%d" , &n , &k , &m ) )
		work () ;
	return 0 ;
}