Poj Solution 3065

http://poj.org/problem?id=3065

#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 - %dn", ans, m-ans );
            
            break;
        }

    }
    return 0;
}