Header Ad

HackerEarth Minimum Nodes problem solution

In this HackerEarth Minimum Nodes problem solution You are given a tree with N nodes and each node has some value assigned to it. Now you are given Q tasks of the form X K.
For each task, you have to find the path starting from X such that sum of nodes in the path is at least K and it contains minimum number of nodes. If such path exists, print the count of nodes in the path, else print -1.


HackerEarth Minimum Nodes problem solution


HackerEarth Minimum Nodes problem solution.

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 4e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;

const int N=1e5+7;
vector<int>g[N];
ll a[N],k;
int ans,n,q;

void dfs(int node,int par,ll sum,int cnt) {
sum+=a[node];
cnt++;
if(sum>=k) ans=min(ans,cnt);
for(int i=0;i<g[node].size();i++) {
int nxt=g[node][i];
if(nxt==par) continue;
dfs(nxt,node,sum,cnt);
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in09.txt","r",stdin);
freopen("out09.txt","w",stdout);
#endif
cin>>n>>q;
assert(n>=1 && n<=100000);
assert(q>=1 && q<=10);
for(int i=1;i<=n;i++) {
cin>>a[i];
assert(a[i]>=1 && a[i]<=1000000000);
}
for(int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
assert(u>=1 && u<=n);
assert(v>=1 && v<=n);
g[u].pb(v);
g[v].pb(u);
}
while(q--) {
int src;
cin>>src>>k;
ans=INT_MAX;
dfs(src,0,0,0);
if(ans==INT_MAX) ans=-1;
cout<<ans<<endl;
}

return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int val[100005],n,q,r,k;
vector<int>v[100005];
bool vis[100005];
int fin=100005;
void init()
{
fin=100005;
for(int i=1;i<=100000;i++)vis[i]=0;
}
void dfs(int r,int value,int cnt)
{
if(value-val[r]<=0){fin=min(fin,cnt+1);return;}
vis[r]=1;cnt++;bool f=0;
for(auto i:v[r])
{
if(vis[i])continue;
dfs(i,value-val[r],cnt);
}
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>val[i];
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
v[y].push_back(x);
v[x].push_back(y);
}
while(q--)
{
init();
cin>>r>>k;
dfs(r,k,0);
cout<<fin<<"\n";
}
return 0;
}

Post a Comment

0 Comments