WA in "Bank Cooperation" (CDUTSV01)

Revision en1, by vaibnak7, 2020-01-10 16:13:56

This recent problem Bank Cooperation, from a codechef contest is solved using bit manipulation in editorial but i think it is solvable by this graph approach too.

All 8 items can be thought as nodes in graph, where the paired up elements will form one component, now in components we cannot take neighbouring nodes, as they can`t be put together.So I found the maximum value that we can take from a component by doing modified dfs, and then added the maximum values of all the components.

I have thought of many cases but cant figure out why its wrong, please help…

My Code

 #include<bits/stdc++.h>
 using namespace std;

 vector<vector<int>>gr(8);
 bool vs[8];
 int A[8];

 void dfs(int v,vector<int>& tmp){
	if(vs[v]){
	   return;
	}
	vs[v] = true;
	tmp.pb(v);
	for(auto i:gr[v]){
	    dfs(i,tmp);
	}
	return;
 }

 void spdfs(int v, int f, int& s){
	if(vs[v]){
		return;
	}
	vs[v] = true;
	if(f){
	        s += A[v];
	}
	for(auto i:gr[v]){
		spdfs(i,1-f,s);
	}
	return;
 }
 
int main(){

	// int t = 1;
	int t;
	cin>>t;

	while(t--){
		
		for(int i=0;i<8;i++){
			cin>>A[i];
			gr[i].clear();		
		}
		int p;
		cin>>p;
		for(int i=0;i<p;i++){
			int a,b;
			cin>>a>>b;
			if(a == b){
				continue;
			}
			a--;
			b--;
			gr[a].pb(b);
			gr[b].pb(a);
		}
		memset(vs, false , sizeof vs);
		vector<vector<int>>cmp;
		for(int i=0;i<8;i++){
			if(vs[i]){
				continue;
			}else{
				vector<int>tmp;
				dfs(i,tmp);
				cmp.pb(tmp);
			}
		}
			
		ll ttl = 0;
		for(int i=0;i<cmp.size();i++){
			int toadd = INT_MIN;
			for(int j=0;j<cmp[i].size();j++){
				memset(vs, false,sizeof vs);
				int tmp = 0;
				spdfs(cmp[i][j], 1, tmp);
				toadd = max(toadd,tmp);	
			}
			ttl += toadd;
		}

		cout<<ttl<<endl;

	  }

		return 0;
	}
	
Tags #graph, #bitmask

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vaibnak7 2020-01-10 16:13:56 1937 Initial revision (published)