fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4.  
  5. //3/25/12 12:33 PM
  6. //by Abrackadabra
  7.  
  8. public class D {
  9.     public static void main(String[] args) throws IOException {
  10.         if (args.length > 0 && args[0].equals("Abra")) debugMode = true;
  11.         new D().run();
  12.     }
  13.  
  14.     int IOMode = 0; //0 - consoleIO, 1 - <taskName>.in/out, 2 - input.txt/output.txt, 3 - test case generator
  15.     String taskName = "";
  16.  
  17.     int n, m;
  18.     ArrayList<TreeSet<Integer>> map = new ArrayList<TreeSet<Integer>>();
  19.  
  20.     void solve() throws IOException {
  21.         n = nextInt();
  22.         m = nextInt();
  23.         for (int i = 0; i < n; i++) {
  24.             map.add(new TreeSet<Integer>());
  25.         }
  26.         for (int i = 0; i < m; i++) {
  27.             int a = nextInt() - 1, b = nextInt() - 1;
  28.             map.get(a).add(b);
  29.             map.get(b).add(a);
  30.         }
  31.         from = new long[n][n];
  32.         depth = new long[n][n];
  33.         sum1 = new long[n][n];
  34.         sum2 = new long[n][n];
  35.         for (int i = 0; i < n; i++)
  36.             bfs(i);
  37.         int R = nextInt();
  38.         HashMap<Long, Integer> nums = new HashMap<Long, Integer>();
  39.         for (int i = 0; i < R; i++) {
  40.             int k = nextInt();
  41.             int[] p = new int[k];
  42.             for (int j = 0; j < k; j++)
  43.                 p[j] = nextInt() - 1;     /*
  44.             Stack<Integer> path = new Stack<Integer>();
  45.             path.add(p[k - 1]);
  46.             for (int j = k - 2; j >= 0; j--) {
  47.                 int t = p[j + 1];
  48.                 while (t != p[j]) {
  49.                     t = from[p[j]][t];
  50.                     path.add(t);
  51.                 }
  52.             }
  53.             int sum = 0, c = 1;
  54.             while (!path.empty()) {
  55.                 int t = path.pop() + 1;
  56.                 sum += t * c;
  57.                 c++;
  58.             }              */
  59.             long ssum = 0;
  60.             int cd = 1;
  61.             for (int j = 0; j < k - 1; j++) {
  62.                 ssum += sum1[p[j]][p[j + 1]] + (cd - 1) * sum2[p[j]][p[j + 1]];
  63.                 cd += depth[p[j]][p[j + 1]] - 1;
  64.                 ssum -= cd * (p[j + 1] + 1);
  65.             }
  66.             ssum += cd * (p[k - 1] + 1);
  67.             if (!nums.containsKey(ssum)) {
  68.                 nums.put(ssum, 1);
  69.             } else {
  70.                 nums.put(ssum, nums.get(ssum) + 1);
  71.             }
  72.             int q = nums.get(ssum);
  73.             out.print(ssum);
  74.             if (q > 1) out.print("#" + q);
  75.             out.println();
  76.         }
  77.     }
  78.  
  79.     long[][] from;
  80.     long[][] depth;
  81.     long[][] sum1;
  82.     long[][] sum2;
  83.  
  84.     void bfs(int x) {
  85.         boolean[] visited = new boolean[n];
  86.         visited[x] = true;
  87.         from[x][x] = -1l;
  88.         depth[x][x] = 1l;
  89.         sum1[x][x] = (x + 1l);
  90.         sum2[x][x] = (x + 1l);
  91.         Queue<Integer> queue = new LinkedList<Integer>();
  92.         queue.add(x);
  93.         while (queue.size() > 0) {
  94.             int a = queue.poll();
  95.             for (int b : map.get(a)) {
  96.                 if (!visited[b]) {
  97.                     visited[b] = true;
  98.                     queue.add(b);
  99.                     from[x][b] = a;
  100.                     depth[x][b] = depth[x][a] + 1;
  101.                     sum1[x][b] = sum1[x][a] + depth[x][b] * (b + 1);
  102.                     sum2[x][b] = sum2[x][a] + b + 1;
  103.                 }
  104.             }
  105.         }
  106.     }
  107.  
  108.     long startTime = System.nanoTime(), tempTime = startTime, finishTime = startTime;
  109.     long startMem = Runtime.getRuntime().totalMemory(), finishMem = startMem;
  110.  
  111.     void run() throws IOException {
  112.         init();
  113.         if (debugMode) {
  114.             con.println("Start");
  115.             con.println("Console:");
  116.         }
  117.         solve();
  118.         finishTime = System.nanoTime();
  119.         finishMem = Runtime.getRuntime().totalMemory();
  120.         out.flush();
  121.         if (debugMode) {
  122.             int maxSymbols = 1000;
  123.             BufferedReader tbr = new BufferedReader(new FileReader("input.txt"));
  124.             char[] a = new char[maxSymbols];
  125.             tbr.read(a);
  126.             if (a[0] != 0) {
  127.                 con.println("File input");
  128.                 con.println(a);
  129.                 if (a[maxSymbols - 1] != 0) con.println("...");
  130.             }
  131.             tbr = new BufferedReader(new FileReader("output.txt"));
  132.             a = new char[maxSymbols];
  133.             tbr.read(a);
  134.             if (a[0] != 0) {
  135.                 con.println("File output");
  136.                 con.println(a);
  137.                 if (a[maxSymbols - 1] != 0) con.println("...");
  138.             }
  139.             con.println("Execution time: " + (finishTime - startTime) / 1000000000.0 + " sec");
  140.             con.println("Used memory:    " + (finishMem - startMem) + " bytes");
  141.             con.println("Total memory:   " + Runtime.getRuntime().totalMemory() + " bytes");
  142.         }
  143.     }
  144.  
  145.     boolean tick(double x) {
  146.         if (System.nanoTime() - tempTime > x * 1e9) {
  147.             tempTime = System.nanoTime();
  148.             con.println("Tick at " + (tempTime - startTime) / 1000000000 + " sec");
  149.             con.print("   ");
  150.             return true;
  151.         }
  152.         return false;
  153.     }
  154.  
  155.     static boolean debugMode = false;
  156.     PrintStream con = System.out;
  157.  
  158.     void init() throws IOException {
  159.         if (debugMode && IOMode != 3) {
  160.             br = new BufferedReader(new FileReader("input.txt"));
  161.             out = new PrintWriter(new FileWriter("output.txt"));
  162.         } else
  163.             switch (IOMode) {
  164.                 case 0:
  165.                     br = new BufferedReader(new InputStreamReader(System.in));
  166.                     out = new PrintWriter(System.out);
  167.                     break;
  168.                 case 1:
  169.                     br = new BufferedReader(new FileReader(taskName + ".in"));
  170.                     out = new PrintWriter(new FileWriter(taskName + ".out"));
  171.                     break;
  172.                 case 2:
  173.                     br = new BufferedReader(new FileReader("input.txt"));
  174.                     out = new PrintWriter(new FileWriter("output.txt"));
  175.                     break;
  176.                 case 3:
  177.                     out = new PrintWriter(new FileWriter("input.txt"));
  178.                     break;
  179.             }
  180.     }
  181.  
  182.     BufferedReader br;
  183.     PrintWriter out;
  184.     StringTokenizer in;
  185.  
  186.     boolean hasMoreTokens() throws IOException {
  187.         while (in == null || !in.hasMoreTokens()) {
  188.             String line = br.readLine();
  189.             if (line == null) return false;
  190.             in = new StringTokenizer(line);
  191.         }
  192.         return true;
  193.     }
  194.  
  195.     String nextString() throws IOException {
  196.         return hasMoreTokens() ? in.nextToken() : null;
  197.     }
  198.  
  199.     int nextInt() throws IOException {
  200.         return Integer.parseInt(nextString());
  201.     }
  202.  
  203.     long nextLong() throws IOException {
  204.         return Long.parseLong(nextString());
  205.     }
  206.  
  207.     double nextDouble() throws IOException {
  208.         return Double.parseDouble(nextString());
  209.     }
  210. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:8: class D is public, should be declared in a file named D.java
public class D {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/bfFeB
language:
Java (HotSpot 12)
created:
12 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!