Generalized Independent Sets

The problem statement says: Finally, for each v, we must have 0 <= f(v) <= 1.

Further, the input specifications don't specify that f(vi) would be in this range.

What should we output if there is NO BAD CYCLE, but f(v) > 1 (in the input) for some ISOLATED VERTEX v?

Did you read the last line of the input section?

Oops :P

I am not able to understand second case, sum of the cycle is 2.00 and floor of 5 node is also 2.00.

How is this bad cycle ?

Thanks,

Arunabh

sum of cycle is not 2.001

i meant, it is 2.001  .

sorry my bad, thanks

what is this man...............

#include <cstdio>
#include <algorithm>
using namespace std;
 
class RadixHeap{
	struct node_t{
		int key;
		int bucket;
		node_t **left, *right;
	} *node, *buckets[30];
	int capacity, B;
	int upper[30];
	void prepend(node_t *n){
		n->left=&buckets[n->bucket];
		if((n->right=buckets[n->bucket]))
			n->right->left=&n->right;
		buckets[n->bucket]=n;
	}
	public:
	void clear(){
		for(int i=0; i<B-1; i++)
			upper[i]=(1<<i)-1;
		upper[B-1]=~(1<<31);
		for(int i=0; i<B; i++)
			buckets[i]=NULL;
	}
	RadixHeap(int sz, int hi){
		node=new node_t[sz];
		capacity=sz;
		B=0;
		while(hi>=1<<B)
			B++;
		B+=2;
		clear();
	}
	~RadixHeap(){
		delete[] node;
	}
	void insert(int v, int k){
		int b=B-1;
		while(b>0 && upper[b-1]>=k)
			b--;
		node[v].key=k;
		node[v].bucket=b;
		prepend(node+v);
	}
	void decrease_key(int v, int k){
		node[v].key=k;
		if(upper[node[v].bucket-1]>=k){
			*node[v].left=node[v].right;
			if(node[v].right)
				node[v].right->left=node[v].left;
			do{
				node[v].bucket--;
			}while(node[v].bucket>0 && upper[node[v].bucket-1]>=k);
			prepend(node+v);
		}
	}
	int delete_min(){
		if(!buckets[0]){
			int b=1;
			while(b<B && buckets[b]==NULL)
				b++;
			if(b==B)
				return -1;
			int mk=buckets[b]->key;
			for(node_t *n=buckets[b]->right; n; n=n->right)
				mk=min(mk, n->key);
			upper[0]=mk;
			for(int i=1; i<b; i++)
				upper[i]=min(upper[i-1]+(1<<(i-1)), upper[b]);
			for(node_t *n=buckets[b], *next; n; n=next){
				next=n->right;
				do{
					n->bucket--;
				}while(n->bucket>0 && upper[n->bucket-1]>=n->key);
				prepend(n);
			}
			buckets[b]=NULL;
		}
		int ret=buckets[0]-node;
		if((buckets[0]=buckets[0]->right))
			buckets[0]->left=buckets;
		return ret;
	}
};
 
void go(){
	int N, M;
	int v[500];
	pair<pair<int, int>, int> edges[8000];
	int edgestart[1001];
	scanf("%d %d", &N, &M);
	for(int i=0; i<N; i++){
		double d;
		scanf("%lf", &d);
		v[i]=1000*d+.01;
	}
	int done=0;
	int MM=0;
	for(int i=0; i<M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		if(!done){
			if(v[x]+v[y]>1000){
				printf("Bad Cycle: %d %d -1n", x, y);
				done=true;
			}
			if(v[x] && v[y]){
				edges[MM++]=make_pair(make_pair(x, y+N), 1000-(v[x]+v[y]));
				edges[MM++]=make_pair(make_pair(x+N, y), 1000-(v[x]+v[y]));
				edges[MM++]=make_pair(make_pair(y, x+N), 1000-(v[x]+v[y]));
				edges[MM++]=make_pair(make_pair(y+N, x), 1000-(v[x]+v[y]));
			}
		}
	}
	if(done)
		return;
	sort(edges, edges+MM);
	edgestart[0]=0;
	for(int i=1; i<=2*N; i++){
		edgestart[i]=edgestart[i-1];
		while(edgestart[i]<MM && edges[edgestart[i]].first.first<i)
			edgestart[i]++;
	}
	RadixHeap rh(2*N, 1000);
	for(int i=0; i<N; i++){
		rh.clear();
		int dist[1000], back[1000];
		fill(dist, dist+2*N, -1);
		dist[i]=0;
		rh.insert(i, 0);
		int next;
		while((next=rh.delete_min())!=-1 && next!=i+N){
			for(int e=edgestart[next]; e<edgestart[next+1]; e++){
				int t=edges[e].first.second;
				int s=dist[next]+edges[e].second;
				if(t!=i && s<1000){
					if(dist[t]==-1){
						dist[t]=s;
						back[t]=next;
						rh.insert(t, s);
					}else if(dist[t]>s){
						dist[t]=s;
						back[t]=next;
						rh.decrease_key(t, s);
					}
				}
			}
		}
		if(dist[i+N]!=-1){
			for(char mark[500]={0}; !mark[next%N]; next=back[next])
				mark[next%N]=1;
			int start=next;
			next=(next+N)%(2*N);
			printf("Bad Cycle: ");
			for(; next!=start; next=back[next])
				printf("%d ", next%N);
			printf("-1n");
			return;
		}
	}
	puts("Ok");
}
 
int main(){
	int T;
	for(scanf("%d", &T); T--; )
		go();
	return 0;
}