OJ Board

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.

accepted

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

Durjoy
Try to use Vector
i got it accepted using vector

Durjoy
remove ur code if u got accepted

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

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

Taman wrote:Thanks to Arifcsecu. . .ur reply to Durjay helped me a lot. . .

It is OK

Input:AC output POSSIBLE

Accepted.

Use class Main

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

brianfry713 wrote:Use class Main

Remove line 72:
count --;