qwerty787788

MapTask

Feb 22nd, 2013
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 11.16 KB | None | 0 0
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class Map {
  6.     FastScanner in;
  7.     PrintWriter out;
  8.  
  9.     class Answer {
  10.         int[] parents;
  11.         int[] size;
  12.         long inside;
  13.         int length;
  14.  
  15.         public Answer(int[] parents, int[] size, long inside, int length) {
  16.             super();
  17.             this.parents = parents;
  18.             this.size = size;
  19.             this.inside = inside;
  20.             this.length = length;
  21.         }
  22.  
  23.         @Override
  24.         public String toString() {
  25.             return "Answer [parents=" + Arrays.toString(parents) + ", size="
  26.                     + Arrays.toString(size) + ", inside=" + inside
  27.                     + ", length=" + length + "]";
  28.         }
  29.  
  30.     }
  31.  
  32.     class ConsistOf {
  33.         String[] s;
  34.  
  35.         public ConsistOf(String[] s) {
  36.             super();
  37.             this.s = s;
  38.         }
  39.  
  40.     }
  41.  
  42.     HashMap<String, ConsistOf> consOf = new HashMap<String, Map.ConsistOf>();
  43.     HashMap<String, Answer> hm = new HashMap<String, Map.Answer>();
  44.  
  45.     class Dsu {
  46.         int n;
  47.         int[] sz;
  48.         int[] p;
  49.  
  50.         Dsu(int n) {
  51.             this.n = n;
  52.             sz = new int[n];
  53.             p = new int[n];
  54.             for (int i = 0; i < n; i++)
  55.                 p[i] = i;
  56.         }
  57.  
  58.         Dsu(int[] p1, int[] p2, int[] p3, int[] p4, int[] sz1, int[] sz2,
  59.                 int[] sz3, int[] sz4) {
  60.             this.n = p1.length * 4;
  61.             sz = new int[n];
  62.             p = new int[n];
  63.             int offset = n / 4;
  64.             for (int i = 0; i < p1.length; i++) {
  65.                 p[i] = p1[i];
  66.                 sz[i] = sz1[i];
  67.             }
  68.             for (int i = 0; i < p1.length; i++) {
  69.                 p[i + offset] = offset + p2[i];
  70.                 if (p2[i] == -1)
  71.                     p[i + offset] = -1;
  72.                 sz[i + offset] = sz2[i];
  73.             }
  74.             offset += n / 4;
  75.             for (int i = 0; i < p1.length; i++) {
  76.                 p[i + offset] = offset + p3[i];
  77.                 if (p3[i] == -1)
  78.                     p[i + offset] = -1;
  79.                 sz[i + offset] = sz3[i];
  80.             }
  81.             offset += n / 4;
  82.             for (int i = 0; i < p1.length; i++) {
  83.                 p[i + offset] = offset + p4[i];
  84.                 if (p4[i] == -1)
  85.                     p[i + offset] = -1;
  86.                 sz[i + offset] = sz4[i];
  87.             }
  88.         }
  89.  
  90.         int get(int v) {
  91.             return (p[v] == v || p[v] == -1) ? p[v] : (p[v] = get(p[v]));
  92.         }
  93.  
  94.         void union(int v1, int v2) {
  95.             v1 = get(v1);
  96.             v2 = get(v2);
  97.             if (v1 == v2 || v1 == -1 || v2 == -1)
  98.                 return;
  99.             if (sz[v1] < sz[v2]) {
  100.                 int tmp = v1;
  101.                 v1 = v2;
  102.                 v2 = tmp;
  103.             }
  104.             if (sz[v1] == sz[v2])
  105.                 sz[v1]++;
  106.             p[v2] = v1;
  107.         }
  108.     }
  109.  
  110.     int[] x = { 0, 1, 1, 0 };
  111.     int[] y = { 1, 1, 0, 0 };
  112.  
  113.     int get(int x1, int y1) {
  114.         for (int i = 0; i < 4; i++)
  115.             if (x[i] == x1 && y[i] == y1)
  116.                 return i;
  117.         return -1;
  118.     }
  119.  
  120.     Answer getAnswer(String name) {
  121.         if (hm.containsKey(name))
  122.             return hm.get(name);
  123.         ConsistOf cons = consOf.get(name);
  124.         if (cons.s[0].equals("0") || cons.s[0].equals("1")) {
  125.             Dsu dsu = new Dsu(4);
  126.             if (cons.s[0].equals("0"))
  127.                 dsu.p[3] = -1;
  128.             if (cons.s[1].equals("0"))
  129.                 dsu.p[2] = -1;
  130.             if (cons.s[2].equals("0"))
  131.                 dsu.p[0] = -1;
  132.             if (cons.s[3].equals("0"))
  133.                 dsu.p[1] = -1;
  134.             char[][] c = new char[2][2];
  135.             c[0][0] = cons.s[0].charAt(0);
  136.             c[0][1] = cons.s[1].charAt(0);
  137.             c[1][0] = cons.s[2].charAt(0);
  138.             c[1][1] = cons.s[3].charAt(0);
  139.             for (int y1 = 0; y1 < 2; y1++)
  140.                 for (int x1 = 0; x1 < 2; x1++)
  141.                     for (int y2 = 0; y2 < 2; y2++)
  142.                         for (int x2 = 0; x2 < 2; x2++) {
  143.                             if (y1 != y2 || x1 != x2)
  144.                                 if (Math.abs(y1 - y2) + Math.abs(x1 - x2) == 1)
  145.                                     if (c[y1][x1] == '1')
  146.                                         if (c[y2][x2] == '1')
  147.                                             dsu.union(get(x1, y1), get(x2, y2));
  148.                         }
  149.             for (int i = 0; i < 4; i++)
  150.                 dsu.get(i);
  151.             Answer ans = new Answer(dsu.p, dsu.sz, 0, 2);
  152.             hm.put(name, ans);
  153.         } else {
  154.             Answer a1 = getAnswer(cons.s[0]);
  155.             Answer a2 = getAnswer(cons.s[1]);
  156.             Answer a3 = getAnswer(cons.s[2]);
  157.             Answer a4 = getAnswer(cons.s[3]);
  158.             int n = a1.length;
  159.              
  160.             Dsu dsu = new Dsu(a1.parents, a2.parents, a3.parents, a4.parents,
  161.                     a1.size, a2.size, a3.size, a4.size);
  162.             for (int i = 0; i < n; i++) {
  163.                 dsu.union(i, 11 * (n - 1) - i);
  164.                 dsu.union(i + (n - 1) * 4, (n - 1) * 15 - i);
  165.                 if (i != 0) {
  166.                     dsu.union(i + (n - 1), (n - 1) * 8 - i);
  167.                     dsu.union(i + (n - 1) * 9, (n - 1) * 16 - i);
  168.                 } else {
  169.                     dsu.union(n - 1, (n - 1) * 4);
  170.                     dsu.union((n - 1) * 9, (n - 1) * 12);
  171.                 }
  172.             }
  173.             for (int i = 0; i < dsu.n; i++)
  174.                 dsu.get(i);
  175.             int[] parents = new int[(n * 2 - 1) * 4];
  176.             int[] size = new int[(n * 2 - 1) * 4];
  177.             long inside = a1.inside + a2.inside + a3.inside + a4.inside;
  178.             int[] id = new int[(n * 2 - 1) * 4];
  179.             for (int i = 0; i < n; i++) {
  180.                 id[i] = (n - 1) * 8 + i;
  181.  
  182.                 id[i + (n * 2 - 1)] = (n - 1) * 13 + i;
  183.  
  184.                 id[i + 2 * (n * 2 - 1)] = (n - 1) * 6 + i;
  185.  
  186.                 if (i != n - 1) {
  187.                     id[i + 3 * (n * 2 - 1)] = (n - 1) * 3 + i;
  188.                 } else {
  189.                     id[i + 3 * (n * 2 - 1)] = 0;
  190.                 }
  191.             }
  192.  
  193.             for (int i = 0; i < n - 1; i++) {
  194.                 id[i + n] = (n - 1) * 12 + i;
  195.  
  196.                 id[i + (n * 2 - 1) + n] = (n - 1) * 5 + i;
  197.  
  198.                 id[i + 2 * (n * 2 - 1) + n] = (n - 1) * 2 + i;
  199.  
  200.                 id[i + 3 * (n * 2 - 1) + n] = (n - 1) * 11 + i;
  201.             }
  202.             for (int i = 0; i < id.length; i++) {
  203.                 parents[i] = dsu.p[id[i]];
  204.                 size[i] = dsu.sz[id[i]];
  205.             }
  206.             HashSet<Integer> was = new HashSet<Integer>();
  207.             was.add(-1);
  208.             for (int i = 0; i < parents.length; i++)
  209.                 was.add(parents[i]);
  210.             for (int i = 0; i < dsu.n; i++) {
  211.                 int x = dsu.get(i);
  212.                 if (!was.contains(x)) {
  213.                     was.add(x);
  214.                     inside++;
  215.                 }
  216.             }
  217.             boolean[] isOnSide = new boolean[dsu.n];
  218.             int[] backId = new int[dsu.n];
  219.             for (int i = 0; i < id.length; i++) {
  220.                 isOnSide[id[i]] = true;
  221.                 backId[id[i]] = i;
  222.             }
  223.             int[] next = new int[dsu.n];
  224.             for (int i = 0; i < next.length; i++)
  225.                 if (isOnSide[i])
  226.                     next[i] = backId[i];
  227.                 else
  228.                     next[i] = -1;
  229.             for (int i = 0; i < id.length; i++)
  230.                 if (parents[i] != -1)
  231.                     if (next[parents[i]] == -1) {
  232.                         size[i] = dsu.sz[parents[i]];
  233.                         next[parents[i]] = i;
  234.                     }
  235.             for (int i = 0; i < parents.length; i++)
  236.                 if (parents[i] != -1)
  237.                     parents[i] = next[parents[i]];
  238.             Answer ans = new Answer(parents, size, inside, n * 2);
  239.             hm.put(name, ans);
  240.         }
  241.         return hm.get(name);
  242.     }
  243.  
  244.     void solve() {
  245.  
  246.         while (true) {
  247.             try {
  248.                 String s = in.br.readLine();
  249.                 if (s == null || s.length() == 0)
  250.                     break;
  251.                 String name = s.substring(0, s.indexOf("="));
  252.                 s = s.substring(s.indexOf("=") + 1);
  253.                 String[] all = new String[4];
  254.                 for (int it = 0; it < 4; it++) {
  255.                     int end = s.indexOf(",");
  256.                     if (end == -1)
  257.                         end = s.length();
  258.                     all[it] = s.substring(0, end);
  259.                     if (it != 3)
  260.                         s = s.substring(end + 1);
  261.                 }
  262.                 consOf.put(name, new ConsistOf(all));
  263.             } catch (IOException e) {
  264.                 break;
  265.             }
  266.         }
  267.         Answer a = getAnswer("Map");
  268.         long ans = a.inside;
  269.         HashSet<Integer> hs = new HashSet<Integer>();
  270.         for (int i = 0; i < 4 * (a.length - 1); i++)
  271.             if (a.parents[i] != -1)
  272.                 hs.add(a.parents[i]);
  273.         ans += hs.size();
  274.         out.println(ans);
  275.     }
  276.  
  277.     void run() {
  278.         try {
  279.             in = new FastScanner(new File("map.in"));
  280.             out = new PrintWriter(new File("map.out"));
  281.  
  282.             solve();
  283.  
  284.             out.close();
  285.         } catch (FileNotFoundException e) {
  286.             e.printStackTrace();
  287.         }
  288.     }
  289.  
  290.     void runIO() {
  291.  
  292.         in = new FastScanner(System.in);
  293.         out = new PrintWriter(System.out);
  294.  
  295.         solve();
  296.  
  297.         out.close();
  298.     }
  299.  
  300.     class FastScanner {
  301.         BufferedReader br;
  302.         StringTokenizer st;
  303.  
  304.         public FastScanner(File f) {
  305.             try {
  306.                 br = new BufferedReader(new FileReader(f));
  307.             } catch (FileNotFoundException e) {
  308.                 e.printStackTrace();
  309.             }
  310.         }
  311.  
  312.         public FastScanner(InputStream f) {
  313.             br = new BufferedReader(new InputStreamReader(f));
  314.         }
  315.  
  316.         String next() {
  317.             while (st == null || !st.hasMoreTokens()) {
  318.                 String s = null;
  319.                 try {
  320.                     s = br.readLine();
  321.                 } catch (IOException e) {
  322.                     e.printStackTrace();
  323.                 }
  324.                 if (s == null)
  325.                     return null;
  326.                 st = new StringTokenizer(s);
  327.             }
  328.             return st.nextToken();
  329.         }
  330.  
  331.         boolean hasMoreTokens() {
  332.             while (st == null || !st.hasMoreTokens()) {
  333.                 String s = null;
  334.                 try {
  335.                     s = br.readLine();
  336.                 } catch (IOException e) {
  337.                     e.printStackTrace();
  338.                 }
  339.                 if (s == null)
  340.                     return false;
  341.                 st = new StringTokenizer(s);
  342.             }
  343.             return true;
  344.         }
  345.  
  346.         int nextInt() {
  347.             return Integer.parseInt(next());
  348.         }
  349.  
  350.         long nextLong() {
  351.             return Long.parseLong(next());
  352.         }
  353.     }
  354.  
  355.     public static void main(String[] args) {
  356.         new Map().run();
  357.     }
  358. }
Advertisement
Add Comment
Please, Sign In to add comment