rendered paste body/* Bartosz Kula bartosz_kula 4 109215 */
/**********************************************************************
* Project : SPOJ TFIBRE (c) copyright
* Org : Gdansk Univeristy of Technology / ETI / group 4
* File : tfibre.c
* Author : student / Bartosz Kula / 109215 / bartosz_kula(at)o2.pl
* Date : 09.05.2007
* About : siec
*----------------------------------------------------------------------
* History:
* ---
* Todo:
* ---
***********************************************************************/
#include <stdio.h>
#include <stdlib.h>
//shashowane numery
unsigned int ip1, ip2;
int wykorzystane_grupy;
int BIG = 1000000;
//budowa struktury do przetrzymywania nrow ipTEST
typedef struct ip
{
int nr_ip;
struct ip *nastepny;
}ip;
ip *wsk;
ip *ADR[50000];
int *HASH[10000000], i = 0, GRUPY[50000], mark = 0;
//zamiana nr ip na nr hashujacy
void zamien_ip(char *IP)
{
//przesylam do funkcji string z IP1 i IP2
unsigned int wynik = 0, pom[3], i = 0, j = 0;
char *wsk;
wsk = IP;
while(*wsk != '\0')
{
//For zamienia do pom[i] char na int.
for( i = 0 ; i < 4; i++ )
{
if( *wsk == '.' || *wsk == '\0' || *wsk == ' ')
{
wsk++;
break;
}
else
{
pom[i] = *wsk - 48;
wsk++;
}
}
//w zaleznosci od ilosci wykonan petli
//zamienia odpowiednio na wynik
if( i == 1 )
wynik = pom[0];
else if ( i == 2 )
wynik = pom[0] * 10 + pom[1];
else if ( i == 3 )
wynik = pom[0] * 100 + pom[1] * 10 + pom[2];
i = 0;
//tutaj przesuwam wynik o odpowiednia ilosc bitow
if(j == 0)
ip1 = (wynik<<24);
else if(j == 1)
ip1 += (wynik<<16);
else if(j == 2)
ip1 += (wynik<<8);
else if(j == 3)
ip1 += wynik;
else if(j == 4)
ip2 = (wynik<<24);
else if(j == 5)
ip2 += (wynik<<16);
else if(j == 6)
ip2 += (wynik<<8);
else if(j == 7)
ip2 += wynik;
wynik = 0;
j++;TEST
}
ip1 %= BIG;
ip2 %= BIG;TEST
}
//sprawdzanie nr ip w tablicy hashujacej
int sprawdz_ip()
{
if( HASH[ip1] == 0 && HASH[ip2] == 0 )
return 1;
if( HASH[ip1] != 0 && HASH[ip2] == 0 )
return 2;
if( HASH[ip1] == 0 && HASH[ip2] != 0 )
return 3;
if( HASH[ip1] != 0 && HASH[ip2] != 0 )
return 4;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("i.txt","r",stdin);
freopen("o.txt","w",stdout);
#endif ONLINE_JUDGE
char opcja,IP[30];
for(i = 1; i < 50000; i++)
GRUPY[i] = i;
while(opcja = getc(stdin))
{
if(opcja == EOF)
break;
else if(opcja == 'B')
{
getchar();
gets(IP);
zamien_ip(IP);
switch(sprawdz_ip())
{
//oba adresy nie naleza do zadnej grupy
//utworz grupe
//polacz elementy
case 1:
{
HASH[ip1] = &GRUPY[wykorzystane_grupy];
HASH[ip2] = &GRUPY[wykorzystane_grupy];
//dodanie wezla IP1 do grupy
ip *nowy1;
nowy1 = (ip*)malloc(sizeof(ip));
nowy1 -> nr_ip = ip1;
ADR[wykorzystane_grupy] = nowy1;
//dodanie wezla IP2 do grupy
ip *nowy2;
nowy2 = (ip*)malloc(sizeof(ip));
nowy2 -> nr_ip = ip2;
nowy1 -> nastepny = nowy2;
nowy2 -> nastepny = NULL;
wykorzystane_grupy++;
}
break;
//pierwszy adres nalezy do grupy
//dowiaz drugi adres do konca pierwszej grupy
//zaktualizuj numery grup adresow IP
case 2:
{
//nadanie ip2 tego samego numeru grupy co ip1
HASH[ip2] = HASH[ip1];
ip *ostatni;
//ustawia wskaznik na adres pierwszego
//elementu w danej grupie i leci do konca
int grupa = *HASH[ip1];
ostatni = ADR[grupa];
while(ostatni -> nastepny != NULL)
ostatni = ostatni -> nastepny;
ip *nowy;
nowy = (ip*)malloc(sizeof(ip));
nowy -> nr_ip = ip2;
nowy -> nastepny = NULL;
ostatni -> nastepny = nowy;
}
break;
//drugi adres nalezy do grupy
//dowiaz pierwszy adres do drugiego
case 3:
{
HASH[ip1] = HASH[ip2];
ip *ostatni;
int grupa = *HASH[ip2];
ostatni = ADR[grupa];
while(ostatni -> nastepny != NULL)
ostatni = ostatni -> nastepny;
ip *nowy;
nowy = (ip*)malloc(sizeof(ip));
nowy -> nr_ip = ip1;
nowy -> nastepny = NULL;
ostatni -> nastepny = nowy;
}
break;
//oba adresy naleza do grup
//polacz grupy
case 4:
{
//wskazniki na elementy obu grup:
ip *grupa1, *grupa2;
grupa1 = ADR[*HASH[ip1]];
grupa2 = ADR[*HASH[ip2]];
//petla wybierajaca krotszy ciag polaczen ip
//(zeby nie updatowac dluzszego ciagu w HASH)
while(mark==0)
{
if(grupa1->nastepny != NULL)
grupa1 = grupa1->nastepny;
else
{
mark=1;
break;
}
if(grupa2->nastepny != NULL)
grupa2 = grupa2->nastepny;
else
{
mark=2;
break;
}
}
//krotsza grupa1, dowiaz do drugiej pierwsza
if(mark==1) //krotsza grupa1
{
grupa1 = ADR[*HASH[ip1]];
grupa2 -> nastepny = grupa1; //zwiazanie grup
while(grupa1 -> nastepny != NULL)
{
HASH[grupa1 -> nr_ip] = HASH[ip2]; //update tab haszujacej
grupa1 = grupa1 -> nastepny;
}
}
else //krotsza grupa2, dowiaz do pierwszej druga
{
grupa2 = ADR[*HASH[ip2]];
grupa1 -> nastepny = grupa2; //zwiazanie grup
while(grupa2 -> nastepny != NULL)
{
HASH[grupa2 -> nr_ip] = HASH[ip1]; //update tab haszujacej
grupa2 = grupa2 -> nastepny;
}
}
mark = 0;
}
break;
default:
break;
}
}
else if(opcja == 'T')
{
getchar();
gets(IP);
zamien_ip(IP);
if(HASH[ip1] == HASH[ip2])
printf("T ");
else
printf("N ");
}
}
return 0;
}