fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class R485PD {
  5.  
  6.     static FastInput k = new FastInput(System.in);
  7.     static FastOutput z = new FastOutput();
  8.  
  9.     static int nodes, edges, kk, s;
  10.  
  11.     static Graph graph;
  12.     static ArrayList<Integer> [] types;
  13.     static int [] nodeTypes;
  14.     static int [][] data;
  15.  
  16.     static void startAlgorithm() {
  17.     	for(int type = 1; type<=kk; type++) {
  18.     		graph.bfs(type);
  19.     	}
  20.  
  21.     	for(int i = 0; i<nodes; i++) {
  22.     		int sum = 0;
  23.  
  24.     		ArrayList<Integer> temp = new ArrayList<Integer>();
  25.     		for(int j = 0; j<data[i].length; j++) {
  26.     			if(data[i][j] != 0) {
  27.     				temp.add(data[i][j]);
  28.     			}
  29.     		}
  30.  
  31.     		Collections.sort(temp);
  32.  
  33.     		for(int j = 0; j<s-1; j++) {
  34.     			sum += temp.get(j);
  35.     		}
  36.  
  37.     		if (i != 0) z.print(" ");
  38. 			z.print(sum);
  39.     	}
  40.  
  41.     	z.println();
  42.     	z.flush();
  43.     }
  44.  
  45.     @SuppressWarnings("unchecked")
  46. 	static void getInputsAndInitializes() {
  47.     	nodes = k.nextInt();
  48.     	edges = k.nextInt();
  49.  
  50.     	kk = k.nextInt();
  51.     	s = k.nextInt();
  52.  
  53.     	graph = new Graph(nodes, edges);
  54.     	data = new int[nodes][kk+1];
  55.     	types = new ArrayList[kk+1];
  56.     	nodeTypes = new int[nodes];
  57.  
  58.     	for(int i = 0; i<kk+1; i++) {
  59.     		types[i] = new ArrayList<Integer>();
  60.     	}
  61.  
  62.     	for(int i = 0; i<nodes; i++) {
  63.     		int type = k.nextInt();
  64.     		types[type].add(i);
  65.     		nodeTypes[i] = type;
  66.     	}
  67.  
  68.     	//i.inputArray(goodType, nodes, InputType.INTEGER);
  69.     	k.inputUndirectedGraph(graph, edges);
  70.     }
  71.  
  72. 	public static void main(String [] args) throws FileNotFoundException {        
  73.         while(k.hasNext()) {
  74.         	getInputsAndInitializes();
  75.         	startAlgorithm();
  76.         }
  77. 	}
  78.  
  79.  
  80. 	/* MARK: InputType enum */
  81.  
  82. 	public enum InputType {
  83. 		INTEGER, LONG, WORD, LINE;
  84. 	}
  85.  
  86.  
  87. 	/* MARK: PrintType enum */
  88.  
  89. 	public enum PrintType {
  90. 		SIDEBYSIDE, LINEBYLINE;
  91. 	}
  92.  
  93.  
  94. 	/* MARK: Graph implementation */
  95.  
  96. 	public static class Graph {
  97. 		int nodes, edges;
  98. 		ArrayList<Integer> [] neighbors;
  99.  
  100. 		@SuppressWarnings("unchecked")
  101. 		public Graph(int nodes) {
  102. 			this.nodes = nodes;
  103. 			neighbors = new ArrayList[nodes];
  104.  
  105. 			initializeGraph();
  106. 		}
  107.  
  108. 		@SuppressWarnings("unchecked")
  109. 		public Graph(int nodes, int edges) { 
  110. 			this.nodes = nodes;
  111. 			this.edges = edges;
  112. 			neighbors = new ArrayList[nodes];
  113.  
  114. 			initializeGraph();
  115. 		}
  116.  
  117. 		public void initializeGraph() {
  118. 			for(int i = 0; i<nodes; i++) {
  119. 				neighbors[i] = new ArrayList<Integer>();
  120. 			}
  121. 		}
  122.  
  123. 		public void addDirectedEdge(int u, int v) {
  124. 			neighbors[u].add(v);
  125. 		}
  126.  
  127. 		public void addUndirectedEdge(int u, int v) {
  128. 			neighbors[u].add(v);
  129. 			neighbors[v].add(u);
  130. 		}
  131.  
  132. 		public void bfs(int type) {
  133.  
  134. 			int [] d = new int[nodes];
  135. 			Arrays.fill(d, Integer.MAX_VALUE);
  136.  
  137. 			MyArrayDeque q = new MyArrayDeque();
  138. 			for(int i = 0; i<types[type].size(); i++) {
  139. 				int node = types[type].get(i);
  140. 				q.enqueue(node);
  141. 				d[node] = 0;
  142. 			}
  143.  
  144. 			while(!q.isEmpty()) {
  145. 				int u = q.dequeue();
  146. 				for(int i = 0; i<neighbors[u].size(); i++) {
  147. 					int v = neighbors[u].get(i);
  148. 					if(d[v] > d[u] + 1 && nodeTypes[v] != type) {
  149. 						d[v] = d[u] + 1;
  150. 						q.enqueue(v);
  151. 						data[v][type] = d[v];							
  152. 					}
  153. 				}
  154. 			}
  155. 		}
  156. 	}
  157.  
  158.  
  159. 	/* MARK: MyArrayDeque implementation */
  160.  
  161. 	public static class MyArrayDeque {
  162. 		int [] queue;
  163. 		int frontCursor;
  164. 		int backCursor;
  165.  
  166. 		public MyArrayDeque() {
  167. 			queue = new int[nodes+1];
  168. 			frontCursor = 0;
  169. 			backCursor = 0;
  170. 		}
  171.  
  172. 		public boolean isEmpty() {
  173. 			return backCursor > frontCursor;
  174. 		}
  175.  
  176. 		public void enqueue(int value) {
  177. 			queue[frontCursor] = value;
  178. 			frontCursor++;
  179. 		}
  180.  
  181. 		public int dequeue() {
  182. 			int returnValue = queue[backCursor];
  183. 			backCursor++;
  184.  
  185. 			return returnValue;
  186. 		}
  187. 	}
  188.  
  189.     /* MARK: FastInput and FastOutput implementation */
  190.  
  191.     public static class FastInput {
  192.         BufferedReader reader;
  193.         StringTokenizer tokenizer;
  194.  
  195.         public FastInput(InputStream stream){
  196.             reader = new BufferedReader(new InputStreamReader(stream));
  197.         }
  198.  
  199. 	    public FastInput(String path){
  200. 	        try {
  201. 	        	reader = new BufferedReader(new FileReader(path));
  202. 			} catch (FileNotFoundException e) {
  203. 				// TODO Auto-generated catch block
  204. 				e.printStackTrace();
  205. 			}
  206. 	        tokenizer = null;
  207. 	    }
  208.  
  209.         public String next() {
  210.             return nextToken();
  211.         }
  212.  
  213.         public String nextLine() {
  214.             try {
  215. 				return reader.readLine();
  216. 			} catch (IOException e) {
  217. 				// TODO Auto-generated catch block
  218. 				e.printStackTrace();
  219. 			}
  220.  
  221.             return null;
  222.         }
  223.  
  224.         public boolean hasNext(){
  225.             try {
  226.                 return reader.ready();
  227.             } catch (IOException e) {
  228.                 // TODO Auto-generated catch block
  229.                 e.printStackTrace();
  230.             }
  231.             return false;
  232.         }
  233.  
  234.         public String nextToken() {
  235.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  236.                 String line = null;
  237.                 try {
  238.                     line = reader.readLine();
  239.                 } catch (IOException e) {
  240.                     throw new RuntimeException(e);
  241.                 }
  242.                 if (line == null) {
  243.                     return null;
  244.                 }
  245.                 tokenizer = new StringTokenizer(line);
  246.             }
  247.             return tokenizer.nextToken();
  248.         }
  249.  
  250.         public Integer nextInt() {
  251.             return Integer.parseInt(nextToken());
  252.         }
  253.  
  254.         public Long nextLong() {
  255.             return Long.valueOf(nextToken());
  256.         }
  257.  
  258.     	public void inputDirectedGraph(Graph graph, int edges) {
  259.     		while(edges--> 0) {
  260.     			int u = k.nextInt(); u--;
  261.     			int v = k.nextInt(); v--;
  262.  
  263.     			graph.addDirectedEdge(u, v);
  264.     		}
  265.     	}
  266.  
  267.     	public void inputUndirectedGraph(Graph graph, int edges) {
  268.     		while(edges--> 0) {
  269.     			int u = k.nextInt(); u--;
  270.     			int v = k.nextInt(); v--;
  271.  
  272.     			graph.addUndirectedEdge(u, v);
  273.     		}
  274.     	}
  275.  
  276.     	public <T> void inputList(ArrayList<T> list, int size, InputType inputType) {
  277.     		switch (inputType) {
  278. 	    		case INTEGER:
  279. 	    			inputIntegerList(list, size); break;
  280. 	    		case LONG:
  281. 	    			inputLongList(list, size); break;
  282. 	    		case WORD:
  283. 	    			inputWordList(list, size); break;
  284. 	    		case LINE:
  285. 	    			inputLineList(list, size); break;
  286. 	    		default: break;
  287.     		}
  288.     	}
  289.  
  290.     	@SuppressWarnings("unchecked")
  291.     	public <T> void inputIntegerList(ArrayList<T> list, int size) {
  292.     		for(int i = 0; i<size; i++) {
  293.     			list.add((T)nextInt());
  294.     		}
  295.     	}
  296.  
  297.     	@SuppressWarnings("unchecked")
  298.     	public <T> void inputLongList(ArrayList<T> list, int size) {
  299.     		for(int i = 0; i<size; i++) {
  300.     			list.add((T)nextLong());
  301.     		}
  302.     	}
  303.  
  304.     	@SuppressWarnings("unchecked")
  305.     	public <T> void inputWordList(ArrayList<T> list, int size) {
  306.     		for(int i = 0; i<size; i++) {
  307.     			list.add((T)next());
  308.     		}
  309.     	}
  310.  
  311.     	@SuppressWarnings("unchecked")
  312.     	public <T> void inputLineList(ArrayList<T> list, int size) {
  313.     		for(int i = 0; i<size; i++) {
  314.     			list.add((T)nextLine());
  315.     		}
  316.     	}
  317.  
  318.     	public <T> void inputArray(T [] array, int size, InputType inputType) {
  319.     		switch (inputType) {
  320. 	    		case INTEGER:
  321. 	    			inputIntegerArray(array, size); break;
  322. 	    		case LONG:
  323. 	    			inputLongArray(array, size); break;
  324. 	    		case WORD:
  325. 	    			inputWordArray(array, size); break;
  326. 	    		case LINE:
  327. 	    			inputLineArray(array, size); break;
  328. 	    		default: break;
  329.     		}
  330.     	}
  331.  
  332.     	@SuppressWarnings("unchecked")
  333.     	public <T> void inputIntegerArray(T [] array, int size) {
  334.     		for(int i = 0; i<size; i++) {
  335.     			array[i] = (T)nextInt();
  336.     		}
  337.     	}
  338.  
  339.  
  340.     	@SuppressWarnings("unchecked")
  341.     	public <T> void inputLongArray(T [] array, int size) {
  342.     		for(int i = 0; i<size; i++) {
  343.     			array[i] = (T)nextLong();
  344.     		}
  345.     	}
  346.  
  347.     	@SuppressWarnings("unchecked")
  348.     	public <T> void inputWordArray(T [] array, int size) {
  349.     		for(int i = 0; i<size; i++) {
  350.     			array[i] = (T)next();
  351.     		}
  352.     	}
  353.  
  354.     	@SuppressWarnings("unchecked")
  355.     	public <T> void inputLineArray(T [] array, int size) {
  356.     		for(int i = 0; i<size; i++) {
  357.     			array[i] = (T)nextLine();
  358.     		}
  359.     	}
  360.     }
  361.  
  362.     public static class FastOutput extends PrintWriter {
  363.     	public FastOutput() { 
  364.             super(new BufferedOutputStream(System.out)); 
  365.     	}
  366.  
  367.     	public <T> void printSet(Set<T> set, int size, PrintType printType) {
  368.     		switch (printType) {
  369. 	    		case SIDEBYSIDE:
  370. 	    			printSideBySideSet(set, size); break;
  371. 	    		case LINEBYLINE:
  372. 	    			printLineByLineSet(set, size); break;
  373. 	    		default: break;
  374.     		}
  375.     	}
  376.  
  377.     	public <T> void printSideBySideSet(Set<T> set, int size) {
  378.     		boolean isFirstElementPrinted = false;
  379.     		for(T element : set) {
  380.     			if(!isFirstElementPrinted) {
  381.     				print(element);
  382.     				isFirstElementPrinted = true;
  383.  
  384.     				return;
  385.     			}
  386.     			print(" "+element);
  387.     		}
  388.     		println();
  389.     	}
  390.  
  391.     	public <T> void printLineByLineSet(Set<T> set, int size) {
  392.     		for(T element : set) {
  393.     			println(element);
  394.     		}
  395.     	}
  396.  
  397.     	public <T> void printList(ArrayList<T> list, int size, PrintType printType) {
  398.     		switch (printType) {
  399. 	    		case SIDEBYSIDE:
  400. 	    			printSideBySideList(list, size); break;
  401. 	    		case LINEBYLINE:
  402. 	    			printLineByLineList(list, size); break;
  403. 	    		default: break;
  404.     		}
  405.     	}
  406.  
  407.     	public <T> void printSideBySideList(ArrayList<T> list, int size) {
  408.     		print(list.get(0));
  409.     		for(int i = 1; i<size; i++) {
  410.     			print(" "+list.get(i));
  411.     		}
  412.     		println();
  413.     	}
  414.  
  415.     	public <T> void printLineByLineList(ArrayList<T> list, int size) {
  416.     		for(int i = 0; i<size; i++) {
  417.     			println(list.get(i));
  418.     		}
  419.     	}
  420.  
  421.     	public <T> void printArray(T [] array, int size, PrintType printType) {
  422.     		switch (printType) {
  423. 	    		case SIDEBYSIDE:
  424. 	    			printSideBySideArray(array, size); break;
  425. 	    		case LINEBYLINE:
  426. 	    			printLineByLineArray(array, size); break;
  427. 	    		default: break;
  428.     		}
  429.     	}
  430.  
  431.     	public <T> void printSideBySideArray(T [] array, int size) {
  432.     		print(array[0]);
  433.     		for(int i = 1; i<size; i++) {
  434.     			print(" "+array[i]);
  435.     		}
  436.     		println();
  437.     	}
  438.  
  439.     	public <T> void printLineByLineArray(T [] array, int size) {
  440.     		for(int i = 0; i<size; i++) {
  441.     			println(array[i]);
  442.     		}
  443.     	}
  444.     }
  445. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class R485PD is public, should be declared in a file named R485PD.java
public class R485PD {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/fGjMWD
language:
Java (HotSpot 12)
created:
5 years 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!