fork download 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayDeque;
  5. import java.util.ArrayList;
  6. import java.util.Deque;
  7.  
  8. public class Main {
  9.  
  10. 	private RoomNode[] rooms;
  11. 	private final int passages;
  12.  
  13. 	private long noOfPairsWhichHaveDraughts = 0;
  14. 	private long noOfRoomsWithAtleastOneDraught = 0;
  15.  
  16. 	public Main(BufferedReader in) throws Exception {
  17.  
  18. 		String[] roomAndPassage = in.readLine().split(" ");
  19. 		int noOfRooms = Integer.parseInt(roomAndPassage[0]);
  20. 		passages = Integer.parseInt(roomAndPassage[1]);
  21. 		rooms = new RoomNode[noOfRooms];
  22.  
  23. 		setRoomsWithOpenWindows(in);
  24. 		setPairsWithDraughts(in);
  25. 		findSolution();
  26. 	}	
  27.  
  28.  
  29. 	private void setRoomsWithOpenWindows(BufferedReader in) throws IOException, Exception {	
  30.  
  31. 		int i = 0;
  32. 		String[] line = in.readLine().split(" ");
  33.  
  34. 		for (String roomToken : line) {
  35. 			boolean openWindow = Integer.parseInt(roomToken) == 1? true:false;
  36. 			rooms[i] = new RoomNode(openWindow);
  37. 			i++;
  38. 			if (i>=rooms.length) {break;}
  39. 		}
  40. 	}
  41.  
  42.  
  43. 	private void setPairsWithDraughts(BufferedReader in) throws NumberFormatException, IOException, Exception {
  44.  
  45. 		String line = null;
  46. 		int i = 0;
  47. 		while((line = in.readLine()) != null && !line.isEmpty() && i < passages) {
  48. 			String[] lineTokens = line.split(" ");
  49. 			RoomNode room1 = rooms[Integer.parseInt(lineTokens[0]) - 1];
  50. 			RoomNode room2 = rooms[Integer.parseInt(lineTokens[1]) - 1];
  51. 			room1.links.add(room2);
  52. 			room2.parent = room1;
  53. 			i++;
  54. 		}
  55. 	}
  56.  
  57.  
  58. 	private void findSolution() {
  59.  
  60. 		prune();
  61. 		Deque<RoomNode> stack = new ArrayDeque<>();
  62. 		for (RoomNode room: rooms) {
  63. 			if (room.visited || !room.openWindow) {continue;}
  64.  
  65. 			int openCount = 0;
  66. 			int draughts = 0;
  67. 			stack.clear();
  68. 			stack.push(room);
  69.  
  70. 			while(!stack.isEmpty()) {
  71. 				RoomNode node = stack.pop();
  72. 				if (node.visited) {continue;}
  73. 				if (node.parent != null) {stack.add(node.parent);}
  74. 				if (node.openWindow) {openCount++;}
  75. 				draughts++;
  76. 				stack.addAll(node.links);
  77. 				node.visited = true;
  78. 			}
  79. 			if (openCount > 1) {
  80. 				noOfPairsWhichHaveDraughts += ((openCount * (openCount-1))/2);
  81. 				noOfRoomsWithAtleastOneDraught += draughts;
  82. 			}
  83. 		}
  84. 	}
  85.  
  86.  
  87. 	private void prune() {
  88.  
  89. 		Deque<RoomNode> stack = new ArrayDeque<>();
  90. 		for (RoomNode room: rooms) {
  91. 			if(room.openWindow || room.links.size() > 1) {continue;}
  92.  
  93. 			stack.push(room);
  94. 			while(!stack.isEmpty()) {
  95. 				RoomNode node = stack.pop();
  96. 				if(node.openWindow || node.links.size() > 1) {continue;}
  97. 				if(!node.links.isEmpty() && node.parent == null) {
  98. 					node.links.get(0).parent = null;
  99. 				}
  100. 				if(node.parent != null && node.links.isEmpty()) {
  101. 					node.parent.links.remove(node);
  102. 					stack.push(node.parent);
  103. 				}
  104. 			}
  105. 		}
  106. 	}
  107.  
  108.  
  109. 	public String getSolution() {
  110. 		return noOfPairsWhichHaveDraughts + " " + noOfRoomsWithAtleastOneDraught;
  111. 	}
  112.  
  113.  
  114. 	public static void main(String[] args) {
  115. 		Main draughts;
  116. 		try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))){
  117. 			draughts = new Main(in);
  118. 			System.out.println(draughts.getSolution());
  119. 		} catch (Exception e) {
  120. 			e.printStackTrace();
  121. 		}
  122. 		System.exit(0);
  123. 	}
  124.  
  125.  
  126. 	private class RoomNode {
  127.  
  128. 		private final boolean openWindow;
  129. 		private final ArrayList<RoomNode> links = new ArrayList<>();
  130. 		private RoomNode parent;
  131. 		private boolean visited;
  132.  
  133. 		public RoomNode (boolean openWindow) {
  134.  
  135. 			this.openWindow = openWindow;
  136. 			visited = false;
  137. 			parent = null;
  138. 		}	
  139. 	}
  140. }
  141.  
Success #stdin #stdout #stderr 0.08s 380224KB
comments (?)
stdin 
8 6
1 1 1 1 0 1 1 0
1 2
2 3
2 4
2 5
6 7
7 8
stdout 
7 6
stderr 
java.io.IOException: Permission denied
	at java.io.FileInputStream.close0(Native Method)
	at java.io.FileInputStream.close(FileInputStream.java:326)
	at java.io.BufferedInputStream.close(BufferedInputStream.java:472)
	at sun.nio.cs.StreamDecoder.implClose(StreamDecoder.java:377)
	at sun.nio.cs.StreamDecoder.close(StreamDecoder.java:192)
	at java.io.InputStreamReader.close(InputStreamReader.java:199)
	at java.io.BufferedReader.close(BufferedReader.java:517)
	at Main.main(Main.java:119)
https://ideone.com/1TFT4M
language:
Java (HotSpot 12)
created:
10 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!