# 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;
}

```
This entry was posted in poj. Bookmark the permalink.