Cod sursa(job #542533)

Utilizator costyv87Vlad Costin costyv87 Data 26 februarie 2011 14:35:06
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.88 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f,*g;
struct cp2{int x, y;} TT[100100];
struct cp3{bool b[100100];};
int RG[100100];
int j,r,ss,con,n, m,q,x,y,i;
int v[100100];
typedef bool bf[100100];
vector <cp3> S;
cp3 bif;

int find(int x)
{
	int R, y;

	//merg in sus pe arbore pana gasesc un nod care pointeaza catre el insusi
	for (R = x; TT[R].x != R; R = TT[R].x);

	//aplic compresia drumurilor
	for (; TT[x].x != x;)
	{
		y = TT[x].x;
		TT[x].x = R;
		x = y;
	}
	return R;
}

void unite(int x, int y)
{
	//unesc multimea cu rang mai mic de cea cu rang mai mare
	if (RG[x] > RG[y])
		TT[y].x = x;
			else TT[x].x = y;

	//in caz ca rangurile erau egale atunci cresc rangul noii multimi cu 1
	if (RG[x] == RG[y]) RG[y]++;
}

bool cmp(cp2 i, cp2 j) {
return(i.x<j.x);
}
bool cmp2(cp2 i, cp2 j) {
return (i.y<j.y);
}

void bv(int y, int r) {
S[r].b[y]=true;
if (v[y]) {
if (S[r].b[v[y]]==false)
      bv(v[y],r);
    }
}

int main() {
f=fopen("gossips.in","r");
g=fopen("gossips.out","w");
fscanf(f,"%d%d%d",&n,&m,&q);

for (i = 1; i <= n; i++) {
    TT[i].x = i;
    TT[i].y = i;
    RG[i] = 1;

    }

for (i=1;i<=m;i++) {
    fscanf(f,"%d%d",&x,&y);
    unite(find(x), find(y));
    v[y]=x;
    }

sort(TT+1,TT+n+1,cmp);
con=0; i=1;
while (i<=n) {
    S.push_back(bif);
    while (TT[i].x==TT[i+1].x) {TT[i].x=con; i++;}
    TT[i].x=con;
    i++;
    con++;
    }
sort(TT+1,TT+n+1,cmp2);


for (i=1;i<=q;i++) {
    fscanf(f,"%d%d%d",&ss,&x,&y);
    if (ss==2) {
        r=TT[x].x;
        S[r].b[y]=true;
        if (v[y]) {
            if (!S[r].b[v[y]])
                bv(v[y],r);
            }
        }
    else {
        if (S[TT[x].x].b[y]==true)
            fprintf(g,"YES\n");
        else
            fprintf(g,"NO\n");

        }
    }


fclose(g);
return 0;
}