Wealth Disparity, INOI 2016

Problem Description

Question : Wealth Disparity, INOI 2016

Submit Code : Codechef

Prerequisites

Depth-First Search

Solution

Problem ask us to find maximum value of difference that a node and its ancestor can have.

To find this we will follow steps:

1. We will make tree out of provided parent/manager array.
2. Apply DFS to find minimum wealth of sub-nodes of node i and store it in array minWealth[i].
3. Take maximum of wealth[i] - minWealth[i] to find maximum wealth disparity.

Code

#include<bits/stdc++.h>

using namespace std;

void findMinWealth(vector<int>* adj, vector<int>& wealth, vector<int>& minWealth, int manager){
    int childMinWealth = wealth[manager];
    for(int u : adj[manager]){
        findMinWealth(adj, wealth, minWealth, u);
        childMinWealth = min(childMinWealth, minWealth[u]);
    }
    minWealth[manager] = childMinWealth;
}

int main(){
    int n;
    cin >> n;
    vector<int> wealth(n+1);
    int manager, hojo;
    vector<int> adj[n+1];
    for(int i=1;i<=n;i++)
        cin >> wealth[i];
    for(int i=1;i<=n;i++){
        cin >> manager;
        if(manager != -1)
            adj[manager].push_back(i);
        else
            hojo = i;
    }

    vector<int> minWealth(n+1);
    findMinWealth(adj, wealth, minWealth, hojo);

    int ans = 0;
    for(int i=1;i<=n;i++)
        ans = max(ans, wealth[i] - minWealth[i]);
    cout << ans;
    return 0;
}