fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Codechef
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		// your code goes here
  13.         Scanner scanner = new Scanner(System.in);
  14.  
  15.         int n = scanner.nextInt();
  16.         int m = scanner.nextInt();
  17.  
  18.         List<Integer>[] adj = new ArrayList[n + 1];
  19.         for (int i = 0; i <= n; i++) {
  20.             adj[i] = new ArrayList<>();
  21.         }
  22.  
  23.         int[] val = new int[n + 1];
  24.  
  25.         for (int i = 1; i <= n; i++) {
  26.             val[i] = scanner.nextInt();
  27.         }
  28.         for (int i = 0; i < m; i++) {
  29.             int u = scanner.nextInt();
  30.             int v = scanner.nextInt();
  31.             adj[u].add(v);
  32.             adj[v].add(u);
  33.         }
  34.         scanner.close();
  35.  
  36.         solve(n,adj,val);
  37.  
  38.  
  39. 	}
  40.     public static void solve(int n, List<Integer>[] adj, int[] val) {
  41.         int[] used = new int[n + 1];
  42.  
  43.         int[] max5 = new int[n + 1];
  44.         int [] lvl=new int[n+1];
  45.  
  46.         Queue<Integer> queue = new LinkedList<>();
  47.  
  48.         if(val[1]==5){
  49.             max5[1]=1;
  50.         }
  51.         queue.add(1);
  52.         used[1]=1;
  53.         lvl[1]=0;
  54.  
  55.         while (!queue.isEmpty()) {
  56.             int u = queue.poll();
  57.  
  58.             for (int v : adj[u]) {
  59.                 int vFives=0;
  60.                 if(val[v]==5){
  61.                     vFives=1;
  62.                 }
  63.                 if (used[v] == 0) {
  64.                     lvl[v]=lvl[u]+1;
  65.                     used[v] = 1;
  66.                     max5[v] = max5[u] + vFives;
  67.                     queue.add(v);
  68.                 } 
  69.                 else{
  70.                     if(lvl[v]==lvl[u]+1){
  71.                         int fre5=max5[u]+vFives;
  72.                         max5[v]=Math.max(max5[v],fre5);
  73.                     }
  74.                 }
  75.             }
  76.         }
  77.  
  78.         for (int i = 1; i <= n; i++) {
  79.             System.out.println("Node " + i + " : " + " maxFives=" + max5[i] +" with distance of "+lvl[i] );
  80.         }
  81.     }
  82. }
Success #stdin #stdout 0.26s 60844KB
comments (?)
stdin
copy 
6 6
5 5 5 0 5 5
1 2
1 3
2 6
3 4
4 5
5 6
stdout
copy 
Node 1 :  maxFives=1 with distance of 0
Node 2 :  maxFives=2 with distance of 1
Node 3 :  maxFives=2 with distance of 1
Node 4 :  maxFives=2 with distance of 2
Node 5 :  maxFives=4 with distance of 3
Node 6 :  maxFives=3 with distance of 2
https://ideone.com/rzyuqg
language:
Java (HotSpot 12)
created:
15 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!