IIITV.str()- AGENTPERRY

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!

Function solve()-> For each query (A, P), see if solution exists or the info is present at itself, if not calculate and return queries[{a,p}].

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