SHARE
TWEET

Untitled

a guest May 19th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class Cpm {
  4.         private static class Job {
  5.         String name, color;
  6.         int key, value, mark;
  7.         Set<Job> parent, to, from;
  8.         public Job(String name, int time) {
  9.             this.name = name;
  10.             this.color = "black";
  11.             this.key = this.value = time;
  12.             this.mark = -1;
  13.             this.parent = new HashSet<>();
  14.             this.to = new HashSet<>();
  15.             this.from = new HashSet<>();
  16.         }
  17.         public void changeValue() {
  18.             if(this.key == this.value && this.from.size() > 0) {
  19.                 this.from.forEach(Job :: changeValue);
  20.                 Job u = Collections.max(this.from, (x, y) -> x.value - y.value);
  21.                 this.from.forEach(v -> {
  22.                     if(v.value == u.value)  this.parent.add(v);
  23.                 });
  24.                 this.value += u.value;
  25.             }
  26.         }
  27.         public void makeBlue() {
  28.             this.color = "blue";
  29.             this.to.forEach(v -> {
  30.                 if(!v.color.equals("blue")) v.makeBlue();
  31.             });
  32.         }
  33.         public void makeRed() {
  34.             this.color = "red";
  35.             this.parent.forEach(Job::makeRed);
  36.         }
  37.     }
  38.     private static void dfs(Job v, List<Job> willBeBlue) {
  39.         v.mark = 0;
  40.         for(Job u : v.to) {
  41.             if(u.mark == -1)    dfs(u, willBeBlue);
  42.             else if(u.mark == 0)    willBeBlue.add(u);
  43.         }
  44.         v.mark = 1;
  45.     }
  46.     public static void main(String[] args) {
  47.         Scanner in = new Scanner(System.in);
  48.         Map<String, Job> graph = new Hashtable<>();
  49.         String prev = null;
  50.         while(in.hasNext()) {
  51.             String s = in.next();
  52.             boolean last = false;
  53.             if(!s.equals("<")) {
  54.                 if(s.charAt(s.length() - 1) == ';') {
  55.                     s = s.substring(0, s.length() - 1);
  56.                     last = true;
  57.                 }
  58.                 if(s.lastIndexOf('(') != -1) {
  59.                     int v = Integer.parseInt(s.substring(s.lastIndexOf('(') + 1, s.length() - 1));
  60.                     s = s.substring(0, s.lastIndexOf('('));
  61.                     graph.put(s, new Job(s, v));
  62.                 }
  63.                 if(prev != null) {
  64.                     graph.get(prev).to.add(graph.get(s));
  65.                     graph.get(s).from.add(graph.get(prev));
  66.                 }
  67.                 if(last) prev = null;
  68.                 else prev = s;
  69.             }
  70.         }
  71.         List<Job> willBeBlue = new ArrayList<>();
  72.         graph.values().forEach(v -> {
  73.             if(v.mark == -1)    dfs(v, willBeBlue);
  74.         });
  75.         willBeBlue.forEach(Job :: makeBlue);
  76.         graph.values().forEach(v -> {
  77.             if(!v.color.equals("blue")) v.changeValue();
  78.         });
  79.         Optional<Job> opt = graph.values().stream().filter(v -> !v.color.equals("blue")).max((a, b) -> a.value - b.value);
  80.         Job x = opt.orElse(null);
  81.         graph.values().forEach(v -> {
  82.             if(!v.color.equals("blue") && v.value == x.value)   v.makeRed();
  83.         });
  84.         StringBuilder gr = new StringBuilder();
  85.         gr.append("digraph {" + "\n");
  86.         for(Job v : graph.values()) {
  87.             gr.append("\t" + v.name + "[label = \"" + v.name + "(" + v.key + ")\"");
  88.             if(!v.color.equals("black"))    gr.append(", color = " + v.color);
  89.             gr.append("]" + "\n");
  90.         }
  91.         for(Job v : graph.values())
  92.             for(Job u : v.to) {
  93.                 gr.append("\t" + v.name + " -> " + u.name);
  94.                 if((u.value == v.value + u.key && v.color.equals("red") && u.color.equals("red")) || v.color.equals("blue"))
  95.                     gr.append(" [color = " + v.color + "]");
  96.                 gr.append("\n");
  97.             }
  98.         gr.append("}" + "\n");
  99.         System.out.print(gr);
  100.     }
  101. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top