IIITV.str()- AGENTPERRY

editorial
1

PROBLEM LINK: AGENTPERRY

Author: mugdha273

Editorialist: mugdha273

DIFFICULTY:

MEDIUM-HARD

Prerequisites:

  • knowledge of Tree, DFS and precomputation or slight DP.

EXPLANATION:

Function modified DFS-> Considering buker D as root node in DFS. Starting from Dbunker, go to each bunker and perform the operations for all information such that we precompute it for all nodes and information in a 2d vector “infoPresent”. The code itself is self explanatory and running it over sample test case will give a perfect view (:stuck_out_tongue: or debugger at each break point if you are lazy like me). Coming back to info present, now if at any node we are arriving for the first time to calculate for pair {c,i}, then you would want to store it as it is other wise its time to check wether already present answer is smaller than current one or not. Call this function recursively just like you do in your favourite DFS to flood your graph with answers. This modification was the essence of the solution. Look at the function modified_dfs again!

Another way to say(in detail):

The modified_dfs function first sets the bunkerDdist array at index c to the value of d, and the pc array at index c to the value of l. This is used to compute the minimum distance from D to C for each query.

Next, the function iterates over the list of bunkers that are connected to the current bunker. For each connected bunker, it checks if it is not the parent of the current bunker. If it is not the parent, then the function performs the following steps:

  1. Calls itself recursively with the connected bunker as the current bunker, the current bunker as the parent, the distance from bunker D to the connected bunker incremented by 1, and I as the number of types of information. This is used to compute the minimum distance from D to C for each query.
  2. Updates the infoPresent array with the information present in the connected bunker. It does this by setting the infoPresent array at index c and i to the minimum of the current value and the value at index x and i in the infoPresent array, where x is the connected bunker and i is the information type. This is used to store the information present in each bunker.

The solve function first checks if the result for the current query has already been computed and stored in the queries map. If it has, then the function simply returns the stored result. This is used to improve performance by avoiding recomputing the same query multiple times.

Next, the function checks if the information type p is present in the current bunker a. If it is, then the function sets the ans variable to the value at index a and p in the infoPresent array, which is the bunker where the information type p is present.

Otherwise, the function checks if the current bunker a is the bunker where Dr. Doofenshmirtz lives. If it is, then the function sets the ans variable to -1, which indicates that the information type p is not present in any bunker.

Otherwise, the function sets the ans variable to the result of calling itself recursively with the parent of the current bunker a as the starting bunker, p as the information type, and Dbunker as the bunker where Dr. Doofenshmirtz lives. This is used to compute the minimum distance from D to C by moving to the parent of the current bunker.

Finally, the function inserts the result of the current query into the queries map and returns the result. This is used to store the results of previously computed queries, so that they can be reused later to improve performance.

SOLUTION:

Setter's Solution 

#include <bits/stdc++.h>

#define M 1000000007

#define all(a) (a).begin(), (a).end()

#define pii pair<int, int>

#define vi vector<int>

#define fi first

#define se second

#define ll long long int

using namespace std;

vector<int> bunkerDdist(10000);

vector<int> pc(10000);

vector<vector<int>>infoPresent;

map<pair<int,int>, int>queries;

vector <int> tree[10001];

void modified_dfs(int c, int l, int d, int I)

{

   bunkerDdist[c] = d;

   pc[c] = l;

   for (auto x:tree[c])

   {

       if (x != l)

       {

           modified_dfs(x, c, d + 1, I);

          

           for (int i = 0; i < I; i++)

           {

               if(infoPresent[x][i]>0)

               {

                   if(infoPresent[c][i] == 0)

                       infoPresent[c][i] = infoPresent[x][i];

                   else

                       infoPresent[c][i] = min(infoPresent[c][i], infoPresent[x][i]);

               }

           }

          

       }

   }

}

int solve(int a, int p, int Dbunker)

{

   int ans;

   if (queries.find({a,p}) != queries.end()) {

       return queries[{a,p}];

   }

   if(infoPresent[a][p]) ans = infoPresent[a][p];

   else {

        if(a == Dbunker) ans = -1;

       else ans = solve(pc[a], p, Dbunker);

   }

   queries.insert({{a,p},ans});

   return ans;

}

int main()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

   // freopen("@input.txt","r",stdin);

   // freopen("@out00.txt","w",stdout);

   int n, I, Dbunker;

   cin>>n>>I>>Dbunker;

   n++; I++;

   for (int i = 0; i < n-2; i++)

   {

       int x,y;

       cin>>x>>y;

       tree[x].push_back(y);

       tree[y].push_back(x);

   }

   vector<int>product(n);

   infoPresent.resize(n,vector<int>(I,0));

   for (int i = 1; i < n; i++)

   {

       int p;

       cin>>p;

       product[i]=p;

       infoPresent[i][p]=i;

   }

  

   modified_dfs(Dbunker,-1,0,I);

   int q;

   cin>>q;

  

   for (int i = 0; i < q; i++)

   {

       int a,p;

       cin>>a>>p;

       cout<<solve(a,p,Dbunker)<<endl;

   }

  

   return 0;

}
1 Like