fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.io.InputStream;
  5. import java.io.InputStreamReader;
  6. import java.io.PrintWriter;
  7. import java.math.BigInteger;
  8. import java.util.ArrayList;
  9. import java.util.StringTokenizer;
  10.  
  11. public class Main {
  12.     FastScanner in;
  13. 	PrintWriter out;
  14.  
  15. 	BigInteger minusOne = BigInteger.ONE.negate();
  16.  
  17. 	class Skill {
  18. 		BigInteger min, max;
  19.  
  20. 		public Skill(BigInteger min, BigInteger max) {
  21. 			super();
  22. 			this.min = min;
  23. 			this.max = max;
  24. 		}
  25.  
  26. 		public Skill() {
  27. 			super();
  28. 			this.min = BigInteger.ZERO;
  29. 			this.max = minusOne;
  30. 		}
  31. 	}
  32.  
  33. 	class SpecialSkill {
  34. 		Skill[] skills;
  35.  
  36. 		public SpecialSkill(int n) {
  37. 			super();
  38. 			skills = new Skill[n];
  39. 			for (int i = 0; i < n; i++) {
  40. 				skills[i] = null;
  41. 			}
  42. 		}
  43.  
  44. 		public int compareSkills(SpecialSkill o) {
  45. 			boolean thisGreaterO = false;
  46. 			boolean thisLessO = false;
  47. 			for (int i = 0; i < this.skills.length; i++) {
  48. 				if (this.skills[i] == null || o.skills[i] == null) {
  49. 					continue;
  50. 				}
  51. 				if (this.skills[i].max.compareTo(o.skills[i].min) < 0) {
  52. 					if (this.skills[i].max.equals(minusOne) == false
  53. 							&& o.skills[i].min.equals(minusOne) == false) {
  54. 						thisLessO = true;
  55. 					}
  56. 				}
  57. 				if (this.skills[i].min.compareTo(o.skills[i].max) > 0) {
  58. 					if (this.skills[i].min.equals(minusOne) == false
  59. 							&& o.skills[i].max.equals(minusOne) == false) {
  60. 						thisGreaterO = true;
  61. 					}
  62. 				}
  63. 			}
  64. 			if (thisGreaterO && thisLessO) {
  65. 				return 1000;
  66. 			}
  67. 			if (thisGreaterO) {
  68. 				return 1;
  69. 			} if (thisLessO) {
  70. 				return -1;
  71. 			}
  72. 			return 0;
  73. 		}
  74.  
  75. 		public boolean checkSkill() {
  76. 			for (int i = 0; i < skills.length; i++) {
  77. 				if (skills[i] == null) {
  78. 					continue;
  79. 				}
  80. 				if (skills[i].max.compareTo(skills[i].min) < 0) {
  81. 					if (this.skills[i].max.equals(minusOne) == false
  82. 							&& this.skills[i].min.equals(minusOne) == false) {
  83. 						return false;
  84. 					}
  85. 				}
  86. 			}
  87. 			return true;
  88. 		}
  89. 	}
  90.  
  91. 	ArrayList<Integer>[] graph;
  92. 	int[] was;
  93.  
  94. 	boolean dfs(int cur, int prev) {
  95. 		was[cur] = 1;
  96. 		for(int i : graph[cur]) {
  97. 			if (was[i] == 1) {
  98. 				if (i != prev) {
  99. 					return false;
  100. 				}
  101. 			} else if (was[i] == 0){
  102. 				if (!dfs(i, cur)) {
  103. 					return false;
  104. 				}
  105. 			}
  106. 		}
  107. 		was[cur] = 2;
  108. 		return true;
  109. 	}
  110. 	public void solve() throws IOException {
  111. 		int m = in.nextInt();
  112. 		int n = in.nextInt();
  113. 		graph = new ArrayList[m];
  114. 		for (int i = 0; i < m; i++) {
  115. 			graph[i] = new ArrayList<>();
  116. 		}
  117. 		was = new int[m];
  118. 		SpecialSkill[] specialSkills = new SpecialSkill[m];
  119. 		for (int i = 0; i < m; i++) {
  120. 			specialSkills[i] = new SpecialSkill(n);
  121. 		}
  122. 		for (int i = 0; i < m; i++) {
  123. 			int k = in.nextInt();
  124. 			for (int j = 0; j < k; j++) {
  125. 				int a = in.nextInt() - 1;
  126. 				String cond = in.next();
  127. 				BigInteger b = new BigInteger(in.next());
  128. 				if (cond.equals(">=") == true) {
  129. 					b = b.max(BigInteger.ZERO);
  130. 					if (specialSkills[i].skills[a] == null) {
  131. 						specialSkills[i].skills[a] = new Skill();
  132. 					}
  133. 					if (specialSkills[i].skills[a].min.equals(minusOne)) {
  134. 						specialSkills[i].skills[a].min = b;
  135. 						continue;
  136. 					}
  137. 					specialSkills[i].skills[a].min = specialSkills[i].skills[a].min
  138. 							.max(b);
  139. 				} else {
  140. 					// if (b.compareTo(BigInteger.ZERO) < 0) {
  141. 					// out.println("NO");
  142. 					// return;
  143. 					// }
  144. 					if (specialSkills[i].skills[a] == null) {
  145. 						specialSkills[i].skills[a] = new Skill();
  146. 					}
  147. 					if (specialSkills[i].skills[a].max.equals(minusOne)) {
  148. 						specialSkills[i].skills[a].max = b;
  149. 						continue;
  150. 					}
  151. 					specialSkills[i].skills[a].max = specialSkills[i].skills[a].max
  152. 							.min(b);
  153. 				}
  154. 			}
  155. 			if (!specialSkills[i].checkSkill()) {
  156. 				out.println("NO");
  157. 				return;
  158. 			}
  159. 		}
  160. 		for (int i = 0; i < m; i++) {
  161. 			for (int j = i + 1; j < m; j++) {
  162. 				int temp = specialSkills[i].compareSkills(specialSkills[j]);
  163. 				if (temp == 1000) {
  164. 					out.println("NO");
  165. 					return;
  166. 				} else if (temp == -1) {
  167. 					graph[j].add(i);
  168. 				} else if (temp == 1) {
  169. 					graph[i].add(j);
  170. 				}
  171. 			}
  172. 		}
  173. 		for (int i = 0; i < m; i++) {
  174. 			if (was[i] == 0) {
  175. 				if(!dfs(i, -1)) {
  176. 					out.println("NO");
  177. 					return;
  178. 				}
  179. 			}
  180. 		}
  181. 		out.println("YES");
  182. 	}
  183.  
  184. 	public void run() {
  185. 		try {
  186. 			InputStream inputStream = System.in;
  187. 			in = new FastScanner(inputStream);
  188. 			out = new PrintWriter(System.out);
  189. 			solve();
  190. 			out.close();
  191. 		} catch (IOException e) {
  192. 			e.printStackTrace();
  193. 		}
  194. 	}
  195.  
  196. 	private class FastScanner {
  197. 		BufferedReader br;
  198. 		StringTokenizer st;
  199.  
  200. 		public FastScanner(InputStream is) {
  201. 			br = new BufferedReader(new InputStreamReader(is));
  202. 		}
  203.  
  204. 		public boolean hasNext() {
  205. 			while (st == null || !st.hasMoreTokens()) {
  206. 				try {
  207. 					String line = br.readLine();
  208. 					if (line == null) {
  209. 						return false;
  210. 					}
  211. 					st = new StringTokenizer(line);
  212. 				} catch (IOException e) {
  213. 					e.printStackTrace();
  214. 				}
  215. 			}
  216. 			if (st != null && st.hasMoreTokens()) {
  217. 				return true;
  218. 			}
  219. 			return false;
  220. 		}
  221.  
  222. 		public String next() {
  223. 			if (hasNext()) {
  224. 				return st.nextToken();
  225. 			}
  226. 			return null;
  227. 		}
  228.  
  229. 		public int nextInt() {
  230. 			return Integer.parseInt(next());
  231. 		}
  232.  
  233. 		public long nextLong() {
  234. 			return Long.parseLong(next());
  235. 		}
  236.  
  237. 		public double nextDouble() {
  238. 			return Double.parseDouble(next());
  239. 		}
  240. 	}
  241.  
  242. 	public static void main(String[] args) {
  243. 		new Main().run();
  244. 	}
  245. }
Success #stdin #stdout 0.08s 381184KB
comments (?)
stdin
copy 
3 3
4
1 >= 1
1 <= 2
2 >= 3
2 <= 4
4
2 >= 1
2 <= 2
3 >= 3
3 <= 4
4
1 >= 3
1 <= 4
3 >= 1
3 <= 2
stdout
copy 
NO
https://ideone.com/4wMFYP
language:
Java (12.0.1)
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!