Help in solving march cook-off question of codechef

Revision en1, by ravan, 2018-03-19 13:46:52

Can anyone please tell me what's wrong with my code.I was solving https://www.codechef.com/problems/CO92TREE this question on codechef.I used map to count all the and values encountered in any subset. here is my code:

include<bits/stdc++.h>

using namespace std;

define pb(a) push_back(a)

define mp(a,b) make_pair(a,b)

define sz() size()

define f first

define s second

define rep(i,a,b) for(int i=a;i<b;i++)

define fast_inpt() ios_base::sync_with_stdio(false);cin.tie(NULL);

typedef long long ll; vector adj[100005]; ll ans[100005]; map<ll,ll> dfs(ll node,ll prnt){ map<ll,ll> mp; mp[node]=1; ans[node]=max(ans[node],1ll); for(int i=0;i<adj[node].sz();i++){ if(adj[node][i]==prnt)continue; map<ll,ll>chld=dfs(adj[node][i],node); map<ll,ll> tmp; for(map<ll,ll>::iterator it=chld.begin();it!=chld.end();++it){ for(map<ll,ll>::iterator it2=mp.begin();it2!=mp.end();++it2){ //printf("node=%d,child=%d\n",node,adj[node][i]); ll val1=it->f; ll val2=it2->f; ll val=val1&val2; //printf("val of prnt map=%d,chld map=%d\n",val2,val1); if(tmp.find(val)==tmp.end()){ tmp[val]= (it->s + it2->s); } else{ tmp[val]=max(tmp[val],it->s + it2->s); } ans[val]=max(ans[val],tmp[val]); }

    }
    mp.clear();
    mp.insert(tmp.begin(),tmp.end());
    tmp.clear();
    chld.clear();
    if(mp.find(node)==mp.end()){mp[node]=1;}
}
return mp;

} int main(){ fast_inpt(); int t;cin>>t; int n; while(t--){ memset(ans,0,sizeof(ans)); cin>>n;ll x,y; rep(i,1,n+1){adj[i].clear();} for(int i=0;i<n-1;i++){ cin>>x>>y; adj[x].pb(y);adj[y].pb(x); } dfs(1ll,1ll);ll maxx=1ll*n; for(int i=1;i<=n;i++){ maxx=max(maxx,1ll*i*ans[i]); } cout<<maxx<<"\n"; } }

Tags tree,map

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ravan 2018-03-19 13:49:33 1549
en1 English ravan 2018-03-19 13:46:52 1842 Initial revision (published)