fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class TaskD {
  5.     private final InputReader reader;
  6.     private final OutputWriter writer;
  7.  
  8.     public TaskD(InputReader reader, OutputWriter writer) {
  9.         this.reader = reader;
  10.         this.writer = writer;
  11.     }
  12.  
  13.     public static void main(String[] args) throws FileNotFoundException {
  14.         //InputReader reader = new InputReader(new FileInputStream("/home/lafa/input-10.txt"));
  15.         InputReader reader = new InputReader(System.in);
  16.         //OutputWriter writer = new OutputWriter(new FileOutputStream("/home/lafa/log1"));
  17.         OutputWriter writer = new OutputWriter(System.out);
  18.         new TaskD(reader, writer).run();
  19.         writer.writer.flush();
  20.     }
  21.  
  22.     int[] A, B, C, T;
  23.  
  24.     List<Integer>[] E;
  25.     List<Integer>[] F, RF;
  26.  
  27.     int n, m;
  28.  
  29.     int[] topsort;
  30.     int tpt;
  31.  
  32.     int[] temp2 = new int[2];
  33.  
  34.     int iter;
  35.     int[] was;
  36.  
  37.     void DFS(int x) {
  38.         was[x] = iter;
  39.         for (int y : F[x]) {
  40.             if (was[y] != iter)
  41.                 DFS(y);
  42.         }
  43.         topsort[tpt++] = x;
  44.     }
  45.  
  46.     int[] col;
  47.     void DFS2(int x, int c) {
  48.         was[x] = iter;
  49.         col[x] = c;
  50.         for (int y : RF[x]) {
  51.             if (was[y] != iter)
  52.                 DFS2(y, c);
  53.         }
  54.     }
  55.  
  56.     ArrayList<Integer> enabled = new ArrayList<Integer>();
  57.  
  58.     boolean can(int v) {
  59.         iter++;
  60.         for (int i = 0; i < m; i++) {
  61.             if (T[i] > v) {
  62.                 F[2 * i + 1].add(2 * i);
  63.                 RF[2 * i].add(2 * i + 1);
  64.             }
  65.         }
  66.  
  67.         tpt = 0;
  68.         for (int x = 0; x < 6 * m; x++) {
  69.             if (was[x] != iter) {
  70.                 DFS(x);
  71.             }
  72.         }
  73.  
  74.         if (tpt != 6 * m)
  75.             throw new AssertionError();
  76.         int cur_col = 0;
  77.         iter++;
  78.         for (int i = tpt - 1; i >= 0; i--) {
  79.             int x = topsort[i];
  80.             if (was[x] != iter)
  81.                 DFS2(x, cur_col++);
  82.         }
  83.         enabled.clear();
  84.  
  85.         boolean bad = false;
  86.         for (int i = 0; i < m; i++) {
  87.             if (col[2 * i] == col[2 * i + 1])
  88.                 bad = true;
  89.             if (col[2 * i + 1] > col[2 * i])
  90.                 enabled.add(i);
  91.         }
  92.  
  93.         for (int i = 0; i < m; i++) {
  94.             if (T[i] > v) {
  95.                 F[2 * i + 1].remove(F[2 * i + 1].size() - 1);
  96.                 RF[2 * i].remove(RF[2 * i].size() - 1);
  97.             }
  98.         }
  99.         return !bad;
  100.     }
  101.  
  102.     final int inf = 1000 * 1000 * 1000 + 42;
  103.  
  104.     int[] prv, nxt;
  105.  
  106.     int get_orient(int i, int e) {
  107.         return (A[e] == i) ? 2 * e : 2 * e + 1;
  108.     }
  109.  
  110.     public void run() {
  111.         n = reader.nextInt();
  112.         m = reader.nextInt();
  113.         A = new int[m];
  114.         B = new int[m];
  115.         C = new int[m];
  116.         T = new int[m];
  117.         E = new ArrayList[n];
  118.         for (int i = 0; i < n; i++)
  119.             E[i] = new ArrayList<Integer>();
  120.         for (int i = 0; i < m; i++) {
  121.             A[i] = reader.nextInt() - 1;
  122.             B[i] = reader.nextInt() - 1;
  123.             C[i] = reader.nextInt();
  124.             T[i] = reader.nextInt();
  125.             E[A[i]].add(i);
  126.             E[B[i]].add(i);
  127.         }
  128.         F = new List[6 * m];
  129.         RF = new List[6 * m];
  130.         for (int i = 0; i < 6 * m; i++) {
  131.             F[i] = new ArrayList<Integer>();
  132.             RF[i] = new ArrayList<Integer>();
  133.         }
  134.         was = new int[6 * m];
  135.         topsort = new int[6 * m];
  136.         prv = new int[2 * m];
  137.         nxt = new int[2 * m];
  138.         Arrays.fill(prv, -1);
  139.         Arrays.fill(nxt, -1);
  140.         for (int x = 0; x < n; x++) {
  141.             Collections.sort(E[x], new Comparator<Integer>() {
  142.                 @Override
  143.                 public int compare(Integer a, Integer b) {
  144.                     return Integer.compare(C[a], C[b]);
  145.                 }
  146.             });
  147.             int ea = -1, eb = -1;
  148.             for (int l = 0, r = 0; l < E[x].size(); l = r) {
  149.                 while (r != E[x].size() && C[E[x].get(r)] == C[E[x].get(l)])
  150.                     r++;
  151.                 if (r - l == 1)
  152.                     continue;
  153.                 if (r - l > 2 || ea != -1) {
  154.                     writer.printf("No\n");
  155.                     return;
  156.                 }
  157.                 ea = E[x].get(l);
  158.                 eb = E[x].get(l + 1);
  159.                 F[2 * ea].add(2 * eb + 1);
  160.                 RF[2 * eb + 1].add(2 * ea);
  161.                 F[2 * eb].add(2 * ea + 1);
  162.                 RF[2 * ea + 1].add(2 * eb);
  163.             }
  164.         }
  165.         for (int i = 0; i < n; i++) {
  166.             for (int e : E[i]) {
  167.                 e = get_orient(i, e);
  168.                 prv[e] = nxt[e] = -1;
  169.             }
  170.             for (int j = 0; j < E[i].size() - 1; j++) {
  171.                 int e = E[i].get(j);
  172.                 int f = E[i].get(j + 1);
  173.                 e = get_orient(i, e);
  174.                 f = get_orient(i, f);
  175.                 prv[f] = e;
  176.                 nxt[e] = f;
  177.             }
  178.             for (int e : E[i]) {
  179.                 e = get_orient(i, e);
  180.                 F[2 * m + 2 * e + 0].add(2 * (e / 2) + 0);
  181.                 F[2 * m + 2 * e + 1].add(2 * (e / 2) + 0);
  182.                 RF[2 * (e / 2) + 0].add(2 * m + 2 * e + 0);
  183.                 RF[2 * (e / 2) + 0].add(2 * m + 2 * e + 1);
  184.  
  185.                 if (prv[e] != -1) {
  186.                     F[2 * m + 2 * e + 0].add(2 * m + 2 * prv[e] + 0);
  187.                     RF[2 * m + 2 * prv[e] + 0].add(2 * m + 2 * e + 0);
  188.                     F[2 * (e / 2) + 1].add(2 * m + 2 * prv[e] + 0);
  189.                     RF[2 * m + 2 * prv[e] + 0].add(2 * (e / 2) + 1);
  190.                 }
  191.                 if (nxt[e] != -1) {
  192.                     F[2 * m + 2 * e + 1].add(2 * m + 2 * nxt[e] + 1);
  193.                     RF[2 * m + 2 * nxt[e] + 1].add(2 * m + 2 * e + 1);
  194.                     F[2 * (e / 2) + 1].add(2 * m + 2 * nxt[e] + 1);
  195.                     RF[2 * m + 2 * nxt[e] + 1].add(2 * (e / 2) + 1);
  196.                 }
  197.             }
  198.         }
  199.  
  200.         col = new int[6 * m];
  201.         int ans = 0;
  202.         int l = -1, r = inf;
  203.         //int l = 999755901, r = l + 1;
  204.         //int l = 999522589 - 1, r = 999522589 + 1;
  205.         while (r - l > 1) {
  206.             int q = (l + r) / 2;
  207.             if (can(q)) {
  208.                 r = q;
  209.             } else {
  210.                 l = q;
  211.             }
  212.         }
  213.         if (r == inf) {
  214.             writer.printf("No\n");
  215.         } else {
  216.             can(r);
  217.             writer.printf("Yes\n");
  218.             writer.printf("%d %d\n", r, enabled.size());
  219.             for (int e : enabled)
  220.                 writer.printf("%d ", e + 1);
  221.             writer.printf("\n");
  222.         }
  223.     }
  224.  
  225.  
  226.     static class InputReader {
  227.         public BufferedReader reader;
  228.         public StringTokenizer tokenizer;
  229.  
  230.         public InputReader(InputStream stream) {
  231.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  232.             tokenizer = null;
  233.         }
  234.  
  235.         public String next() {
  236.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  237.                 try {
  238.                     tokenizer = new StringTokenizer(reader.readLine());
  239.                 } catch (IOException e) {
  240.                     throw new RuntimeException(e);
  241.                 }
  242.             }
  243.             return tokenizer.nextToken();
  244.         }
  245.  
  246.         public int nextInt() {
  247.             return Integer.parseInt(next());
  248.         }
  249.  
  250.         public double nextDouble() {
  251.             return Double.parseDouble(next());
  252.         }
  253.  
  254.         public long nextLong() {
  255.             return Long.parseLong(next());
  256.         }
  257.     }
  258.  
  259.     static class OutputWriter {
  260.         public PrintWriter writer;
  261.  
  262.         OutputWriter(OutputStream stream) {
  263.             writer = new PrintWriter(stream);
  264.         }
  265.  
  266.         public void printf(String format, Object... args) {
  267.             writer.print(String.format(Locale.ENGLISH, format, args));
  268.         }
  269.     }
  270. }
  271.  
  272.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class TaskD is public, should be declared in a file named TaskD.java
public class TaskD {
       ^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
stdout
copy 
Standard output is empty
https://ideone.com/bx3QJ8
language:
Java (12.0.1)
created:
8 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!