My problem in Hackerrank Coding Fever #Round 01

Revision en1, by Rifat_Hasan, 2020-04-26 12:52:23

I have recently set a problem for the contest named "Coding Fever #Round 01".

I am inviting you to take a look over the problem statement — Armies are coming Home.

Here is the editorial of my problem:

It is a normal dfs/bfs problem to find the shortest path of the node which contains armies. For finding the cost for returning to home we should add all the sum of shortest path distance. The distance of each node from the root can be calculated as dis[child] = dis[parent]+1. Just one simple observation is here that when we pass a node which contains armies we do not add the distance for the next node so dis[child] will be same as dis[parents], dis[child] = dis[parent]. Here dis is an array for storing the distance from root.

My solution:

#include<bits/stdc++.h>
#define ll long long
#define MAXN 1000006

using namespace std;

int dis[MAXN];
bool vis[MAXN];
bool mark[MAXN];
vector<int>adj[MAXN];
vector<int>ans,vv;

void dfs(int u,int d){
    vis[u]=true;
    dis[u]=d;
    for(int i=0;i<adj[u].size();i++){
        if(!vis[adj[u][i]]){
            if(!mark[u]) d=dis[u]+1;
            else d=dis[u];
            dfs(adj[u][i],d);
        }
    }
    return;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n,k; cin>>n>>k;

    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<k;i++){
        int x; cin>>x;
        mark[x]=1;
        vv.push_back(x);
    }
    dfs(1,0);

    ll res=0;

    for(int i=0;i<k;i++){
        res+=dis[vv[i]];
    }
    cout<<res<<endl;

}
Tags #dfs and similar

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Rifat_Hasan 2020-04-26 12:52:23 1858 Initial revision (published)