Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.io.BufferedReader;
- import java.awt.Point;
- public class buffet{
- public static final String TASKNAME = "buffet";
- public static long mod= 1000000007;
- public static Debug db;
- public static void main(String[] args) throws IOException {
- // InputReader in = new InputReader(System.in);
- PrintWriter out = new PrintWriter(System.out);
- // InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
- InputReader in = new InputReader(new FileInputStream("3.in.txt"));
- // PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
- Autocompletion solver = new Autocompletion();
- db=new Debug(System.getSecurityManager()==null);
- solver.solve(1, in, out);
- out.close();
- }
- static class Autocompletion {
- public void solve(int testNumber, InputReader in, PrintWriter out) {
- int n=in.nextInt();
- int e=in.nextInt();
- ArrayList<Integer>[] adj=new ArrayList[n];
- int quality[]=new int[n];
- int sortedq[]=new int[n];
- for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
- for(int i=0;i<n;i++) {
- int q=in.nextInt();
- quality[i]=q;
- sortedq[i]=q;
- int d=in.nextInt();
- for(int j=0;j<d;j++) {
- adj[i].add(in.nextInt()-1);
- }
- }
- Arrays.sort(sortedq);
- int max[][]=new int[n][n];
- ArrayDeque<Triple> dq=new ArrayDeque<Triple>();
- for(int i=0;i<n;i++) {
- dq.add(new Triple(i,quality[i]));
- max[i][Arrays.binarySearch(sortedq, quality[i])]=quality[i];
- }
- while(!dq.isEmpty()) {
- Triple x=dq.remove();
- for(int y:adj[x.x]) {
- int temp=Arrays.binarySearch(sortedq, quality[y]);
- int temp2=Arrays.binarySearch(sortedq, x.y);
- if(quality[y]>x.y) {
- if(max[y][temp]<max[x.x][temp2]+quality[y]-e) {
- max[y][temp]=max[x.x][temp2]+quality[y]-e;
- dq.add(new Triple(y,quality[y]));
- }
- }
- if(max[y][temp2]<max[x.x][temp2]-e) {
- dq.add(new Triple(y,x.y));
- max[y][temp2]=max[x.x][temp2]-e;
- }
- }
- }
- int ret=0;
- for(int i=0;i<n;i++) {
- for(int j=0;j<n;j++) {
- ret=Math.max(ret, max[i][j]);
- }
- }
- out.println(ret);
- }
- }
- static class Triple implements Comparable<Triple>{
- int x;//node
- int y;//index for qual
- Triple(int a, int b){
- x=a;
- y=b;
- }
- @Override
- public int compareTo(Triple arg0) {
- if(arg0.x!=x)return x-arg0.x;
- return y-arg0.y;
- }
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public int[] nextIntArr(int n) {
- int arr[]=new int[n];
- for(int i=0;i<n;i++) {
- arr[i]=this.nextInt();
- }
- return arr;
- }
- }
- public static class Debug {
- private boolean allowDebug;
- public Debug(boolean allowDebug) {
- this.allowDebug = allowDebug;
- }
- private void outputName(String name) {
- System.out.print(name + " = ");
- }
- public void debug(String name, int x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, long x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, double x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, int[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, long[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, double[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, Object x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, Object... x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.deepToString(x));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement