1 / 1
Oct 2010

This problem was given for kanpur site.
codechef.com/problems/ACMKANPB/

please tell what is wrong with my code ??

#include <iostream>
#include <cstdio>
using namespace std;
int N,M,L;
int adj[110][110]={0};
int getbonus(int root,int* bonus,int* done,int* isvisited){
	if ( isvisited[root])
		return bonus[root];
	isvisited[root]=1;
	if ( done[root]==1)
		return bonus[root];
	int mx=0;
	for ( int i=0;i<N;++i){
		if ( adj[root][i]!=-1 && i!=root)
			mx=getbonus(i,bonus,done,isvisited)+adj[root][i]>mx?getbonus(i,bonus,done,isvisited)+adj[root][i]:mx;
	}
	bonus[root]=mx;
	done[root]=1;
	isvisited[root]=0;
	return mx;
}
bool flag;
void dfs(int root,int* isVisited,int *isVisited2,int count){
	if(isVisited[root]){
		if(count>0)
			flag=true;
		return;
	}
	if(isVisited2[root]) return;
	if(flag) return;
	isVisited[root]=isVisited2[root]=1;
    for (int i=0;i<N;++i){
	if(i==root || adj[root][i]==-1)
		continue;
	dfs(i,isVisited,isVisited2,count+adj[root][i]);
}
isVisited[root]=0;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		flag=false;
		scanf("%d %d %d",&N,&M,&L);
		for(int i=0;i<100;++i)
			for(int j=0;j<100;++j)
				adj[i][j]=-1;
		int son[110]={0};
		int bonus[110]={0};
		int done[110]={0};
		for( int i=0;i<M;++i){
			int x,y,z;
			scanf("%d %d %d",&x,&y,&z);
			son[x-1]=1;
			adj[x-1][y-1]=z;
		}
		/*for(int i=0;i<N;++i)
			if(!son[i]){
				bonus[i]=L;
				done[i]=1;
			}
		*/
		int isvisited[100]={0},isVisited2[100]={0};
		dfs(0,isvisited,isVisited2,0);
		if ( flag){
			printf("Inconsistent analysis.\n");
			continue;
		}
		for(int i=0;i<N;++i)
			isvisited[i]=0;
		for(int i=0;i<N;++i)
			getbonus(i,bonus,done,isvisited);
		int sum=0;
		for(int i=0;i<N;++i)
			sum+=bonus[i]+L;
		printf("%d\n",sum);
		for(int i=0;i<N;++i)
			printf("%d ",bonus[i]+L);
		printf("\n");
	}
return 0;
}

i think it fails for cases like
6 1 10
1 1 2
are there any other cases for which it may fail ??

Suggested Topics

Want to read more? Browse other topics in Off-topic or view latest topics.