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) {
  14.         InputReader reader = new InputReader(System.in);
  15.         OutputWriter writer = new OutputWriter(System.out);
  16.         new TaskD(reader, writer).run();
  17.         writer.writer.flush();
  18.     }
  19.  
  20.     int[] A, B, L;
  21.  
  22.     List<Integer>[] E;
  23.     int n, m;
  24.  
  25.     long[] dij(int s) {
  26.         long[] D = new long[n];
  27.         Arrays.fill(D, (long) 1e18);
  28.         D[s] = 0;
  29.         boolean[] was = new boolean[n];
  30.         long last = -1;
  31.         int pt = 0;
  32.         for (int i = 0; i < n; i++) {
  33.             int mni = -1;
  34.             for (int j = 0; j < n; j++)
  35.                 if (!was[j] && (mni == -1 || D[mni] > D[j]))
  36.                     mni = j;
  37.             if (mni == -1)
  38.                 throw new AssertionError();
  39.             if (D[mni] != last) {
  40.                 last = D[mni];
  41.                 pt++;
  42.             }
  43.             for (int e : E[mni]) {
  44.                 int y = mni ^ A[e] ^ B[e];
  45.                 if (was[y])
  46.                     continue;
  47.                 D[y] = Math.min(D[y], D[mni] + L[e]);
  48.             }
  49.             D[mni] = pt;
  50.             was[mni] = true;
  51.         }
  52.         return D;
  53.     }
  54.  
  55.     long[][] V;
  56.     short[][] cnt;
  57.     long[][] SV;
  58.     short[][] Scnt;
  59.     long get_sum(int x1, int y1, int x2, int y2) {
  60.         x2++;
  61.         y2++;
  62.         return SV[x2][y2] - SV[x2][y1] - SV[x1][y2] + SV[x1][y1];
  63.     }
  64.  
  65.     int get_cnt(int x1, int y1, int x2, int y2) {
  66.         x2++;
  67.         y2++;
  68.         return Scnt[x2][y2] - Scnt[x2][y1] - Scnt[x1][y2] + Scnt[x1][y1];
  69.     }
  70.  
  71.     public void run() {
  72.         n = reader.nextInt();
  73.         m = reader.nextInt();
  74.         int s = reader.nextInt() - 1;
  75.         int t = reader.nextInt() - 1;
  76.         long[] W = new long[n];
  77.         for (int i = 0; i < n; i++)
  78.             W[i] = reader.nextInt();
  79.         A = new int[m];
  80.         B = new int[m];
  81.         L = new int[m];
  82.         E = new List[n];
  83.         for (int i = 0; i < n; i++)
  84.             E[i] = new ArrayList<Integer>(1);
  85.         for (int i = 0; i < m; i++) {
  86.             A[i] = reader.nextInt() - 1;
  87.             B[i] = reader.nextInt() - 1;
  88.             L[i] = reader.nextInt();
  89.             E[A[i]].add(i);
  90.             E[B[i]].add(i);
  91.         }
  92.         long[] Ds = dij(s);
  93.         long[] Dt = dij(t);
  94.         int mxs = -1, mxt = -1;
  95.         for (long d : Ds)
  96.             mxs = (int)Math.max(d, mxs);
  97.         for (long d : Dt)
  98.             mxt = (int)Math.max(d, mxt);
  99.         long[][] DS = new long[mxs + 1][mxt + 1], DT = new long[mxs + 1][mxt + 1];
  100.         V = new long[mxs + 1][mxt + 1];
  101.         cnt = new short[mxs + 1][mxt + 1];
  102.         for (int i = 0; i < n; i++) {
  103.             V[(int) Ds[i]][(int) Dt[i]] += W[i];
  104.             cnt[(int) Ds[i]][(int) Dt[i]]++;
  105.         }
  106.         SV = new long[mxs + 2][mxt + 2];
  107.         Scnt = new short[mxs + 2][mxt + 2];
  108.         for (int i = 0; i < mxs + 1; i++)
  109.             for (int j = 0; j < mxt + 1; j++) {
  110.                 SV[i + 1][j + 1] = SV[i + 1][j] + SV[i][j + 1] - SV[i][j] + V[i][j];
  111.                 Scnt[i + 1][j + 1] = (short)(Scnt[i + 1][j] + Scnt[i][j + 1] - Scnt[i][j] + cnt[i][j]);
  112.             }
  113.  
  114.         for (int i = 0; i <= mxs; i++)
  115.             for (int j = 0; j <= mxt; j++)
  116.                 DS[i][j] = DT[i][j] = (long)-1e15;
  117.         int[] posS = new int[mxt + 1];
  118.         long[] curmnS = new long[mxt + 1];
  119.         int[] posT = new int[mxs + 1];
  120.         long[] curmnT = new long[mxs + 1];
  121.         Arrays.fill(posS, mxs + 1);
  122.         Arrays.fill(posT, mxt + 1);
  123.         Arrays.fill(curmnS, (long)-1e15);
  124.         Arrays.fill(curmnT, (long)-1e15);
  125.         for (int i = mxs; i >= 0; i--)
  126.             for (int j = mxt; j >= 0; j--) {
  127.                 if (get_cnt(i + 1, j + 1, mxs, mxt) == 0) {
  128.                     DS[i][j] = DT[i][j] = 0;
  129.                     continue;
  130.                 }
  131.                 if (get_cnt(i + 1, j + 1, i + 1, mxt) != 0) {
  132.                     while (posS[j] >  i + 1) {
  133.                         posS[j]--;
  134.                         curmnS[j] = Math.max(curmnS[j], get_sum(0, j + 1, posS[j], mxt) - DT[posS[j]][j]);
  135.                     }
  136.                 }
  137.                 if (get_cnt(i + 1, j + 1, mxs, j + 1) != 0) {
  138.                     while (posT[i] > j + 1) {
  139.                         posT[i]--;
  140.                         curmnT[i] = Math.max(curmnT[i], get_sum(i + 1, 0, mxs, posT[i]) - DS[i][posT[i]]);
  141.                     }
  142.                 }
  143.                 DS[i][j] = Math.max(DS[i][j], -get_sum(0, j + 1, i, mxt) + curmnS[j]);
  144.                 DT[i][j] = Math.max(DT[i][j], -get_sum(i + 1, 0, mxs, j) + curmnT[i]);
  145.             }
  146.         long val = DS[0][0];
  147.         if (val > 0)
  148.             writer.printf("Break a heart\n");
  149.         else if (val < 0)
  150.             writer.printf("Cry\n");
  151.         else
  152.             writer.printf("Flowers\n");
  153.     }
  154.  
  155.  
  156.     static class InputReader {
  157.         public BufferedReader reader;
  158.         public StringTokenizer tokenizer;
  159.  
  160.         public InputReader(InputStream stream) {
  161.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  162.             tokenizer = null;
  163.         }
  164.  
  165.         public String next() {
  166.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  167.                 try {
  168.                     tokenizer = new StringTokenizer(reader.readLine());
  169.                 } catch (IOException e) {
  170.                     throw new RuntimeException(e);
  171.                 }
  172.             }
  173.             return tokenizer.nextToken();
  174.         }
  175.  
  176.         public int nextInt() {
  177.             return Integer.parseInt(next());
  178.         }
  179.  
  180.         public double nextDouble() {
  181.             return Double.parseDouble(next());
  182.         }
  183.  
  184.         public long nextLong() {
  185.             return Long.parseLong(next());
  186.         }
  187.     }
  188.  
  189.     static class OutputWriter {
  190.         public PrintWriter writer;
  191.  
  192.         OutputWriter(OutputStream stream) {
  193.             writer = new PrintWriter(stream);
  194.         }
  195.  
  196.         public void printf(String format, Object... args) {
  197.             writer.print(String.format(Locale.ENGLISH, format, args));
  198.         }
  199.     }
  200. }
  201.  
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/0JPkPt
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!