Chef Under Pressure CodeChef Solution

Problem -Chef Under Pressure CodeChef Solution

“ ”

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Chef Under Pressure CodeChef Solution in C

“ ”

#include<stdio.h>
#include<stdlib.h>
struct city{
int ci;
struct city *next;
};

struct city *ptr[10001];

int n,k,p[10001],db[10001][101];

void rec(int prc,int pac)
{
    struct city *temp;
    int j;
    temp=ptr[prc];

    db[prc][p[prc]]=prc;
    while(temp)
    {
        if(temp->ci==pac)
        {
            temp=temp->next;
            continue;
        }

        rec(temp->ci,prc);
        for(j=1;j<=k;j++)
            if(db[prc][j]>db[temp->ci][j])
               db[prc][j]=db[temp->ci][j];
        temp=temp->next;
    }

    return ;



}

void rec1(int prc,int pac)
{

    int j;
    struct city *temp;
    for(j=1;j<=k;j++)
    {
        if(db[prc][j]==n+1)
            db[prc][j]=db[pac][j];
    }
    temp=ptr[prc];
    while(temp)
    {
        if(temp->ci==pac)
        {
            temp=temp->next;
            continue;
        }

        rec1(temp->ci,prc);
        temp=temp->next;



    }



    return;


}




int main()
{
    struct city *temp;
    int q,chci,pr,i,j,x,y,cap;
    scanf("%d",&n);
    scanf("%d",&k);
    scanf("%d",&cap);
    for(i=1;i<=n;i++)
        for(j=1;j<=k;j++)
            db[i][j]=n+1;
    for(i=0;i<n-1;i++)
    {
        scanf("%d",&x);
        scanf("%d",&y);
        //for city x
        temp=(struct city*)malloc(sizeof(struct city));
        temp->ci=y;
        temp->next=ptr[x];
        ptr[x]=temp;

         temp=(struct city*)malloc(sizeof(struct city));
        temp->ci=x;
        temp->next=ptr[y];
        ptr[y]=temp;
    }

  /* for( i=1;i<=n;i++)
   {
       temp=ptr[i];
       while(temp)
       {
           printf("%d ",temp->ci);
           temp=temp->next;
       }
       printf("\n");
   }*/
   for(i=1;i<=n;i++)
    scanf("%d",&p[i]);
   rec(cap,cap);
   rec1(cap,cap);

/*for(i=1;i<=n;i++)
{
        for(j=1;j<=k;j++)
            printf("%d ",db[i][j]);
printf("\n");
}*/


scanf("%d",&q);
  for(i=0;i<q;i++)
  {
      scanf("%d",&chci);
      scanf("%d",&pr);
      if(db[chci][pr]==n+1)
        printf("%d\n",-1);
      else
      printf("%d\n",db[chci][pr]);
  }




return 0;
}

Chef Under Pressure CodeChef Solution in JAVA

“ ”

import java.util.*;
import java.io.*;
 
public class Main {
  
  private static final String NL = System.getProperty("line.separator");
  private static List<List<Integer>> adj, costs;
  private static int N, LN;
  private static int[][] parents;
  private static int[] depths, edges, prod;
  public static void main(String[] args) throws IOException {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] nk = br.readLine().split(" ");
    int N = Integer.parseInt(nk[0]);
    int K = Integer.parseInt(nk[1]);
    int B = Integer.parseInt(br.readLine());
    LN = (int) Math.floor(Math.log(N)/Math.log(2));
    prod = new int[N];
    parents = new int[LN][N];
    depths = new int[N];
    edges = new int[N];  
    adj = new ArrayList<List<Integer>>();
    costs = new ArrayList<List<Integer>>();
    
    for (int i = 0; i < N; i++) {
      List<Integer> a = new ArrayList<Integer>();
      adj.add(a);
      List<Integer> c = new ArrayList<Integer>();
      costs.add(c);
      for (int j = 0; j < LN; j++) parents[j][i] = -1;
    }
    
    for (int i = 0; i < N - 1; i++) {
      String[] xy = br.readLine().split(" ");
      int X = Integer.parseInt(xy[0]) - 1;
      int Y = Integer.parseInt(xy[1]) - 1;
      adj.get(X).add(Y);
      adj.get(Y).add(X);
      costs.get(X).add(1);
      costs.get(Y).add(1);
    }
    
    Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
    for (int i = 0; i < N; i++) {
      int p = Integer.parseInt(br.readLine());
      prod[i] = p;
      List<Integer> list;
      if (map.containsKey(p)) {
        list = map.get(p);
      } else {
        list = new ArrayList<Integer>();
      }
      list.add(i);
      map.put(p, list);
    }
    
    dfs(B - 1);
    for (int i = 1; i < LN; i++)
      for (int j = 0; j < N; j++)
        if (parents[i - 1][j] != -1)
          parents[i][j] = parents[i - 1][parents[i - 1][j]];
    
    int Q = Integer.parseInt(br.readLine());
    for (int i = 0; i < Q; i++) {
      String[] query = br.readLine().split(" ");
      int A = Integer.parseInt(query[0]) - 1;
      int p = Integer.parseInt(query[1]);
      int max = -1;
      int tNode = -2;
      if (map.containsKey(p)) {
        for (int node : map.get(p)) {
          int lca = lca(A, node);
          int d = depths[lca];
          if (d > max) {
            max = d;
            tNode = node;
          }
        }
      }
      System.out.println(tNode + 1);
    }
  }
  
  private static class Node {
    int nodeId;
    int nodeDepth;
    int prevId;
    public Node(int id, int depth, int prev) {
      nodeId = id;
      nodeDepth = depth;
      prevId = prev;
    }
  }
  
  private static void dfs(int B) {
    Deque<Node> stack = new ArrayDeque<Node>();
    depths[B] = 0;
    parents[0][B] = -1;
    edges[B] = -1;
    stack.addFirst(new Node(B, 0, -1));
    while(stack.size() != 0) {
      Node currNode = stack.removeFirst();
      int curr = currNode.nodeId;
      int currDepth = currNode.nodeDepth;
      int prev = currNode.prevId;
      for (int i = 0; i < adj.get(curr).size(); i++) {
        int child = adj.get(curr).get(i);
        if (child != prev) {
          int childCost = costs.get(curr).get(i);
          depths[child] = currDepth + 1;
          edges[child] = childCost;
          parents[0][child] = curr;
          Node childNode = new Node(child, currDepth + 1, curr);
          stack.addFirst(childNode);
        }
      }
    }
  }
  
  private static int lca(int u, int v) {
    if (depths[u] < depths[v]) {
      int tmp = u;
      u = v;
      v = tmp;
    }
    int log = 1;
    for (; 1 << log <= depths[u]; log++);
    log--;
    for (int i = log; i >= 0; i--)
      if (depths[u] - (1 << i) >= depths[v])
        u = parents[i][u];
    if (u == v) return u;
    for (int i = log; i >= 0; i--) {
      if (parents[i][u] != -1 && parents[i][u] != parents[i][v]) {
        u = parents[i][u];
        v = parents[i][v];
      }
    }
    return parents[0][u];
  }
} 

Chef Under Pressure CodeChef Solution in PYTH

“ ”

def dfs(c, l, d):
    distanceFromCapital[c] = d
    pathToCapital[c] = l
    for x in tree[c]:
        if x != l:
            dfs(x, c, d + 1)
            for i in xrange(k):
                if isPresent[x][i] > 0:
                    if isPresent[c][i] == 0:
                        isPresent[c][i] = isPresent[x][i]
                    else:
                        isPresent[c][i] = min(isPresent[c][i], isPresent[x][i])

queries = {}

def solve(a, p):
    if (a, p) in queries:
        return queries[(a, p)]
    if isPresent[a][p]:
        ans = isPresent[a][p]
    else:
        if a == capital:
            ans = -1
        else:
            ans = solve(pathToCapital[a], p)
    queries[(a, p)] = ans
    return ans
        

n, k = map(int, raw_input().split())
n += 1
k += 1

capital = input()

tree = [[] for i in xrange(n)]
for _ in xrange(n - 2):
    x, y = map(int, raw_input().split())
    tree[x].append(y)
    tree[y].append(x)

isPresent = [[0 for i in xrange(k)] for j in xrange(n)]

product = [0 for i in xrange(n)]

for i in xrange(1, n):
    p = input()
    product[i] = p
    isPresent[i][p] = i
    
distanceFromCapital = [0 for i in xrange(n)]
pathToCapital = [0 for i in xrange(n)]

dfs(capital, -1, 0)

q = input()

for i in xrange(q):
    a, p = map(int, raw_input().split())
    print solve(a, p)
    

Chef Under Pressure CodeChef Solution in C#

“ ”

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

// (づ°ω°)づﾐ★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜
class Solver
{
    private int n, m;
    private List<int>[] edges;
    private int[] a;

    private int[] hasDesc;
    int Dfs(int x, int p, int v)
    {
        int min = int.MaxValue;
        foreach (int e in edges[x])
            if (e != p)
            {
                int y = Dfs(e, x, v);
                min = Math.Min(min, y);
            }
        if (a[x] == v)
            min = Math.Min(min, x);
        return hasDesc[x] = min;
    }

    private int[,] b;
    void Dfs2(int x, int p, int v, int y)
    {
        if (hasDesc[x] == int.MaxValue)
            b[x, v] = y;
        else
            b[x, v] = y = hasDesc[x];
        foreach (int e in edges[x])
            if (e != p)
                Dfs2(e, x, v, y);
    }

    public object Solve()
    {
        n = ReadInt();
        m = ReadInt();
        int root = ReadInt() - 1;

        edges = Enumerable.Repeat(0, n).Select(x => new List<int>()).ToArray();
        for (int i = 1; i < n; i++)
        {
            int u = ReadInt() - 1;
            int v = ReadInt() - 1;
            edges[u].Add(v);
            edges[v].Add(u);
        }

        a = new int[n];
        var good = new bool[m];
        for (int i = 0; i < n; i++)
        {
            a[i] = ReadInt() - 1;
            good[a[i]] = true;
        }

        b = new int[n,m];
        for (int i = 0; i < m; i++)
        {
            hasDesc = Enumerable.Repeat(-1, n).ToArray();
            Dfs(root, -1, i);
            Dfs2(root, -1, i, int.MaxValue);
        }

        for (int q = ReadInt(); q > 0; q--)
        {
            int u = ReadInt() - 1;
            int v = ReadInt() - 1;
            writer.WriteLine(good[v] ? b[u, v] + 1 : -1);
        }

        return null;
    }
    
    #region I/O
    protected static TextReader reader;
    protected static TextWriter writer;

    static void Main()
    {
#if DEBUG
        reader = new StreamReader("..\\..\\input.txt");
        writer = Console.Out;
        //writer = new StreamWriter("..\\..\\output.txt");
#else
        reader = Console.In;
        writer = new StreamWriter(Console.OpenStandardOutput());
#endif

        Solver solver = new Solver();

        try
        {
            object result = solver.Solve();
            if (result != null)
            {
                writer.WriteLine(result);
            }
        }
        catch (Exception ex)
        {
#if DEBUG
            Console.WriteLine(ex);
#else
            Console.WriteLine(ex);
            throw;
#endif
        }
        reader.Close();
        writer.Close();
    }

    #endregion

    #region Read/Write

    private static Queue<string> currentLineTokens = new Queue<string>();

    private static string[] ReadAndSplitLine()
    {
        return reader.ReadLine().Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
    }

    public static string ReadToken()
    {
        while (currentLineTokens.Count == 0)
            currentLineTokens = new Queue<string>(ReadAndSplitLine());
        return currentLineTokens.Dequeue();
    }

    public static int ReadInt()
    {
        return int.Parse(ReadToken());
    }

    public static long ReadLong()
    {
        return long.Parse(ReadToken());
    }

    public static double ReadDouble()
    {
        return double.Parse(ReadToken(), CultureInfo.InvariantCulture);
    }

    public static int[] ReadIntArray()
    {
        return ReadAndSplitLine().Select(x => int.Parse(x)).ToArray();
    }

    public static long[] ReadLongArray()
    {
        return ReadAndSplitLine().Select(x => long.Parse(x)).ToArray();
    }

    public static double[] ReadDoubleArray()
    {
        return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray();
    }

    public static int[][] ReadIntMatrix(int numberOfRows)
    {
        int[][] matrix = new int[numberOfRows][];
        for (int i = 0; i < numberOfRows; i++)
            matrix[i] = ReadIntArray();
        return matrix;
    }

    public static int[][] ReadAndTransposeIntMatrix(int numberOfRows)
    {
        int[][] matrix = ReadIntMatrix(numberOfRows);
        int[][] ret = new int[matrix[0].Length][];
        for (int i = 0; i < ret.Length; i++)
        {
            ret[i] = new int[numberOfRows];
            for (int j = 0; j < numberOfRows; j++)
                ret[i][j] = matrix[j][i];
        }
        return ret;
    }

    public static string[] ReadLines(int quantity)
    {
        string[] lines = new string[quantity];
        for (int i = 0; i < quantity; i++)
            lines[i] = reader.ReadLine().Trim();
        return lines;
    }

    public static void WriteArray<T>(params T[] array)
    {
        writer.WriteLine(string.Join(" ", array.Select(x => x.ToString()).ToArray()));
    }

    #endregion
}

Chef Under Pressure CodeChef Solution Review:

In our experience, we suggest you solve this Chef Under Pressure CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Chef Under Pressure CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Chef Under Pressure CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn