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