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 ismy 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<ll> 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";↵
}link to my code:https://www.codechef.com/viewsolution/17911030↵
}
this question on codechef.I used map to count all the and values encountered in any subset.↵
here is
#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<ll> 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";↵
}
