3065.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3065  User Id:fzk 
Memory:23564K  Time:1593MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <algorithm>
using namespace std;

int p[6000010];
int st[6000010];

void clear( int n ) {
	memset( p, -1, sizeof(int)*(n+1) );
}

void input( int &m, int &sa, int &sb ) {
	char w[2];
	m=1;sa=0;sb=1;

	if( scanf( "%1s", w ) != 1 )return;
	ungetc( w[0], stdin );

	if( !(w[0]>='0'&&w[0]<='9'||w[0]=='-') ) {
		return;
	}
	
	scanf( "%d", &m );
	if( scanf( "%1s", w ) != 1 )return;
	ungetc( w[0], stdin );
	if( !(w[0]>='0'&&w[0]<='9'||w[0]=='-') ) {
		return;
	}

	scanf( "%d", &sb );
	if( scanf( "%1s", w ) != 1 )return;
	ungetc( w[0], stdin );
	if( !((w[0]>='0'&&w[0]<='9')||w[0]=='-') ) {
		return;
	}

	scanf( "%d", &sa );
}

int main( ) {
	int n, a, b, m, sa, sb, ans, k, ta, tb, *sn;
	char s[2];

	while( 1 ) {
		if( scanf( "%1s", s ) != 1 )
			break;
		
		switch( s[0] ) {
		case 'D': case 'd':
			scanf( "%d", &n );
			clear( n );
			break;
		case 'C': case 'c':
			scanf( "%d%d", &a, &b );
			input( m, sa, sb );
			
			for( k=0; k<m; a+=sa, b+=sb, k++ ){

				if( p[ta=a] >= 0 ) {
					sn=st;
					do {
						*(sn++) = ta;
						ta = p[ta];
					}while( p[ta] >= 0 );

					while( (sn--)!=st )
						p[*sn] = ta;
				}
				
				if( p[tb=b] >= 0 ) {
					sn=st;
					do{
						*(sn++) = tb;
						tb = p[tb];
					}while( p[tb]>=0 );

					while( (sn--)!=st )
						p[*sn] = tb;
				}
				
				if( ta != tb ) {
					if( p[ta] < p[tb] )
						p[tb] = ta;
					else if( p[ta] > p[tb] )
						p[ta] = tb;
					else {
						p[ta] = tb;
						p[tb]--;
					}
				}
			}
			break;

		case 'Q': case 'q':
			scanf( "%d%d", &a, &b );
			input( m, sa, sb );
			
			ans = 0;
			for( k=0; k<m; a+=sa, b+=sb, k++ ) {
				if( a == b )
					ans ++;
				else
				{
						
					if( p[ta=a] >= 0 ) {
						sn=st;
						do {
							*(sn++) = ta;
							ta = p[ta];
						}while( p[ta] >= 0 );

						while( (sn--)!=st )
							p[*sn] = ta;
					}
					
					if( p[tb=b] >= 0 ) {
						sn=st;
						do{
							*(sn++) = tb;
							tb = p[tb];
						}while( p[tb]>=0 );

						while( (sn--)!=st )
							p[*sn] = tb;
					}
					
					if( ta == tb )
						ans ++;
				}

			}
			printf( "%d - %d\n", ans, m-ans );
			
			break;
		}

	}
	return 0;
}