Advertisement
ec1117

Untitled

Jun 18th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.39 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.io.BufferedReader;
  4. import java.awt.Point;
  5.  
  6. public class buffet{
  7. public static final String TASKNAME = "buffet";
  8. public static long mod= 1000000007;
  9. public static Debug db;
  10.  
  11. public static void main(String[] args) throws IOException {
  12. // InputReader in = new InputReader(System.in);
  13. PrintWriter out = new PrintWriter(System.out);
  14. // InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
  15. InputReader in = new InputReader(new FileInputStream("3.in.txt"));
  16. // PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
  17. Autocompletion solver = new Autocompletion();
  18. db=new Debug(System.getSecurityManager()==null);
  19. solver.solve(1, in, out);
  20. out.close();
  21. }
  22. static class Autocompletion {
  23.  
  24. public void solve(int testNumber, InputReader in, PrintWriter out) {
  25. int n=in.nextInt();
  26. int e=in.nextInt();
  27. ArrayList<Integer>[] adj=new ArrayList[n];
  28. int quality[]=new int[n];
  29. int sortedq[]=new int[n];
  30. for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
  31. for(int i=0;i<n;i++) {
  32. int q=in.nextInt();
  33. quality[i]=q;
  34. sortedq[i]=q;
  35. int d=in.nextInt();
  36. for(int j=0;j<d;j++) {
  37. adj[i].add(in.nextInt()-1);
  38. }
  39. }
  40. Arrays.sort(sortedq);
  41. int max[][]=new int[n][n];
  42. ArrayDeque<Triple> dq=new ArrayDeque<Triple>();
  43. for(int i=0;i<n;i++) {
  44. dq.add(new Triple(i,quality[i]));
  45. max[i][Arrays.binarySearch(sortedq, quality[i])]=quality[i];
  46. }
  47. while(!dq.isEmpty()) {
  48. Triple x=dq.remove();
  49. for(int y:adj[x.x]) {
  50. int temp=Arrays.binarySearch(sortedq, quality[y]);
  51. int temp2=Arrays.binarySearch(sortedq, x.y);
  52. if(quality[y]>x.y) {
  53. if(max[y][temp]<max[x.x][temp2]+quality[y]-e) {
  54. max[y][temp]=max[x.x][temp2]+quality[y]-e;
  55. dq.add(new Triple(y,quality[y]));
  56. }
  57. }
  58. if(max[y][temp2]<max[x.x][temp2]-e) {
  59. dq.add(new Triple(y,x.y));
  60. max[y][temp2]=max[x.x][temp2]-e;
  61. }
  62. }
  63. }
  64. int ret=0;
  65. for(int i=0;i<n;i++) {
  66. for(int j=0;j<n;j++) {
  67. ret=Math.max(ret, max[i][j]);
  68. }
  69. }
  70. out.println(ret);
  71. }
  72. }
  73.  
  74.  
  75. static class Triple implements Comparable<Triple>{
  76. int x;//node
  77. int y;//index for qual
  78. Triple(int a, int b){
  79. x=a;
  80. y=b;
  81. }
  82. @Override
  83. public int compareTo(Triple arg0) {
  84. if(arg0.x!=x)return x-arg0.x;
  85. return y-arg0.y;
  86. }
  87. }
  88. static class InputReader {
  89. public BufferedReader reader;
  90. public StringTokenizer tokenizer;
  91.  
  92. public InputReader(InputStream stream) {
  93. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  94. tokenizer = null;
  95. }
  96.  
  97. public String next() {
  98. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  99. try {
  100. tokenizer = new StringTokenizer(reader.readLine());
  101. } catch (IOException e) {
  102. throw new RuntimeException(e);
  103. }
  104. }
  105. return tokenizer.nextToken();
  106. }
  107.  
  108. public int nextInt() {
  109. return Integer.parseInt(next());
  110. }
  111. public long nextLong() {
  112. return Long.parseLong(next());
  113. }
  114. public int[] nextIntArr(int n) {
  115. int arr[]=new int[n];
  116. for(int i=0;i<n;i++) {
  117. arr[i]=this.nextInt();
  118. }
  119. return arr;
  120. }
  121. }
  122. public static class Debug {
  123. private boolean allowDebug;
  124.  
  125. public Debug(boolean allowDebug) {
  126. this.allowDebug = allowDebug;
  127. }
  128.  
  129. private void outputName(String name) {
  130. System.out.print(name + " = ");
  131. }
  132.  
  133. public void debug(String name, int x) {
  134. if (!allowDebug) {
  135. return;
  136. }
  137.  
  138. outputName(name);
  139. System.out.println("" + x);
  140. }
  141.  
  142. public void debug(String name, long x) {
  143. if (!allowDebug) {
  144. return;
  145. }
  146. outputName(name);
  147. System.out.println("" + x);
  148. }
  149.  
  150. public void debug(String name, double x) {
  151. if (!allowDebug) {
  152. return;
  153. }
  154. outputName(name);
  155. System.out.println("" + x);
  156. }
  157.  
  158. public void debug(String name, int[] x) {
  159. if (!allowDebug) {
  160. return;
  161. }
  162. outputName(name);
  163. System.out.println(Arrays.toString(x));
  164. }
  165.  
  166. public void debug(String name, long[] x) {
  167. if (!allowDebug) {
  168. return;
  169. }
  170. outputName(name);
  171. System.out.println(Arrays.toString(x));
  172. }
  173.  
  174. public void debug(String name, double[] x) {
  175. if (!allowDebug) {
  176. return;
  177. }
  178. outputName(name);
  179. System.out.println(Arrays.toString(x));
  180. }
  181.  
  182. public void debug(String name, Object x) {
  183. if (!allowDebug) {
  184. return;
  185. }
  186. outputName(name);
  187. System.out.println("" + x);
  188. }
  189.  
  190. public void debug(String name, Object... x) {
  191. if (!allowDebug) {
  192. return;
  193. }
  194. outputName(name);
  195. System.out.println(Arrays.deepToString(x));
  196. }
  197. }
  198. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement