11690 - Money Matters

[durjay]

I solve the this problem by DFS. but it is time limit exceed. here is my code:

#include<stdio.h>

long int k1;

long int g[10001][10001]={0},cl[10001];

long int d,cu[10001];

int dfs();

void dfs_visit(int u);

int main()

{

long int u,r,j,a,y;

long int c,s,i,t;

scanf("%ld",&t);

for(i=1;i<=t;i++)

{



scanf("%ld%ld",&u,&r);

d=u;

for(j=0;j<u;j++)

scanf("%ld",&cu[j]);



for(j=0;j<r;j++)

{

scanf("%ld%ld",&a,&y);

g[a][y]=1;

g[y][a]=1;

}

r=dfs();

if(r==0)

printf("IMPOSSIBLE\n");

else

printf("POSSIBLE\n");

for(c=0;c<d;c++)

for(s=0;s<d;s++)

g[c][s]=0;

}

return 0;

}

int dfs()

{



int i;

for(i=0;i<d;i++)

{

cl=1;

}

for(i=0;i<d;i++)

{

if(cl==1)

{

k1=0;

k1=k1+cu;

dfs_visit(i);

if(k1<0)

{

return 0;

break;

}

}

}

return 1;

}



void dfs_visit(int u)

{

int i;

cl=2;



for(i=0;i<d;i++)

{

if(g==1)

{

if(cl==1)

{

k1=k1+cu;

dfs_visit(i);

}

}

}

cl=3;



}

plz help me.

[durjay]

accepted

[Igor9669]

You use a lot of memory(about 400 MB), your solution wouldn't work!

[saiful_sust]

Hi durjay...
Try to solve it with set operation ..............
it is a easy problem..............
Always think easy.........

[arifcsecu]

Durjoy
Try to use Vector
i got it accepted using vector

[saiful_sust]

Durjoy
try it with set operation

u have to find disjoin set and total sum of every set = 0 than it is possible
else impossible

EX: if 1 and 2 is friend, 3 and 4 is friend than there is two set.

but when 2 and 3 is friend than there is 1 set that is {1,2,3};

I think that is enough.............
try it .....

[arifcsecu]

Durjoy
remove ur code if u got accepted

[poixp]

The solution with matrix also works if you chose the correct data type. Long int is overhead.

[Taman]

Thanks to Arifcsecu. . .ur reply to Durjay helped me a lot. . .

[arifcsecu]

Thanks to Arifcsecu. . .ur reply to Durjay helped me a lot. . .

It is OK

[brianfry713]

Input:

Code: Select all

1
5 4
1
1
1
1
-4
0 1
2 3
1 2
3 4

AC output POSSIBLE

[moxlotus]

Accepted.

[brianfry713]

Use class Main

[moxlotus]

My submitted code is using Main. still it didnt work. =(
Do u have any other test cases to help me out ? Thanks

Use class Main

[brianfry713]

Remove line 72:
count --;