Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Map {
- FastScanner in;
- PrintWriter out;
- class Answer {
- int[] parents;
- int[] size;
- long inside;
- int length;
- public Answer(int[] parents, int[] size, long inside, int length) {
- super();
- this.parents = parents;
- this.size = size;
- this.inside = inside;
- this.length = length;
- }
- @Override
- public String toString() {
- return "Answer [parents=" + Arrays.toString(parents) + ", size="
- + Arrays.toString(size) + ", inside=" + inside
- + ", length=" + length + "]";
- }
- }
- class ConsistOf {
- String[] s;
- public ConsistOf(String[] s) {
- super();
- this.s = s;
- }
- }
- HashMap<String, ConsistOf> consOf = new HashMap<String, Map.ConsistOf>();
- HashMap<String, Answer> hm = new HashMap<String, Map.Answer>();
- class Dsu {
- int n;
- int[] sz;
- int[] p;
- Dsu(int n) {
- this.n = n;
- sz = new int[n];
- p = new int[n];
- for (int i = 0; i < n; i++)
- p[i] = i;
- }
- Dsu(int[] p1, int[] p2, int[] p3, int[] p4, int[] sz1, int[] sz2,
- int[] sz3, int[] sz4) {
- this.n = p1.length * 4;
- sz = new int[n];
- p = new int[n];
- int offset = n / 4;
- for (int i = 0; i < p1.length; i++) {
- p[i] = p1[i];
- sz[i] = sz1[i];
- }
- for (int i = 0; i < p1.length; i++) {
- p[i + offset] = offset + p2[i];
- if (p2[i] == -1)
- p[i + offset] = -1;
- sz[i + offset] = sz2[i];
- }
- offset += n / 4;
- for (int i = 0; i < p1.length; i++) {
- p[i + offset] = offset + p3[i];
- if (p3[i] == -1)
- p[i + offset] = -1;
- sz[i + offset] = sz3[i];
- }
- offset += n / 4;
- for (int i = 0; i < p1.length; i++) {
- p[i + offset] = offset + p4[i];
- if (p4[i] == -1)
- p[i + offset] = -1;
- sz[i + offset] = sz4[i];
- }
- }
- int get(int v) {
- return (p[v] == v || p[v] == -1) ? p[v] : (p[v] = get(p[v]));
- }
- void union(int v1, int v2) {
- v1 = get(v1);
- v2 = get(v2);
- if (v1 == v2 || v1 == -1 || v2 == -1)
- return;
- if (sz[v1] < sz[v2]) {
- int tmp = v1;
- v1 = v2;
- v2 = tmp;
- }
- if (sz[v1] == sz[v2])
- sz[v1]++;
- p[v2] = v1;
- }
- }
- int[] x = { 0, 1, 1, 0 };
- int[] y = { 1, 1, 0, 0 };
- int get(int x1, int y1) {
- for (int i = 0; i < 4; i++)
- if (x[i] == x1 && y[i] == y1)
- return i;
- return -1;
- }
- Answer getAnswer(String name) {
- if (hm.containsKey(name))
- return hm.get(name);
- ConsistOf cons = consOf.get(name);
- if (cons.s[0].equals("0") || cons.s[0].equals("1")) {
- Dsu dsu = new Dsu(4);
- if (cons.s[0].equals("0"))
- dsu.p[3] = -1;
- if (cons.s[1].equals("0"))
- dsu.p[2] = -1;
- if (cons.s[2].equals("0"))
- dsu.p[0] = -1;
- if (cons.s[3].equals("0"))
- dsu.p[1] = -1;
- char[][] c = new char[2][2];
- c[0][0] = cons.s[0].charAt(0);
- c[0][1] = cons.s[1].charAt(0);
- c[1][0] = cons.s[2].charAt(0);
- c[1][1] = cons.s[3].charAt(0);
- for (int y1 = 0; y1 < 2; y1++)
- for (int x1 = 0; x1 < 2; x1++)
- for (int y2 = 0; y2 < 2; y2++)
- for (int x2 = 0; x2 < 2; x2++) {
- if (y1 != y2 || x1 != x2)
- if (Math.abs(y1 - y2) + Math.abs(x1 - x2) == 1)
- if (c[y1][x1] == '1')
- if (c[y2][x2] == '1')
- dsu.union(get(x1, y1), get(x2, y2));
- }
- for (int i = 0; i < 4; i++)
- dsu.get(i);
- Answer ans = new Answer(dsu.p, dsu.sz, 0, 2);
- hm.put(name, ans);
- } else {
- Answer a1 = getAnswer(cons.s[0]);
- Answer a2 = getAnswer(cons.s[1]);
- Answer a3 = getAnswer(cons.s[2]);
- Answer a4 = getAnswer(cons.s[3]);
- int n = a1.length;
- Dsu dsu = new Dsu(a1.parents, a2.parents, a3.parents, a4.parents,
- a1.size, a2.size, a3.size, a4.size);
- for (int i = 0; i < n; i++) {
- dsu.union(i, 11 * (n - 1) - i);
- dsu.union(i + (n - 1) * 4, (n - 1) * 15 - i);
- if (i != 0) {
- dsu.union(i + (n - 1), (n - 1) * 8 - i);
- dsu.union(i + (n - 1) * 9, (n - 1) * 16 - i);
- } else {
- dsu.union(n - 1, (n - 1) * 4);
- dsu.union((n - 1) * 9, (n - 1) * 12);
- }
- }
- for (int i = 0; i < dsu.n; i++)
- dsu.get(i);
- int[] parents = new int[(n * 2 - 1) * 4];
- int[] size = new int[(n * 2 - 1) * 4];
- long inside = a1.inside + a2.inside + a3.inside + a4.inside;
- int[] id = new int[(n * 2 - 1) * 4];
- for (int i = 0; i < n; i++) {
- id[i] = (n - 1) * 8 + i;
- id[i + (n * 2 - 1)] = (n - 1) * 13 + i;
- id[i + 2 * (n * 2 - 1)] = (n - 1) * 6 + i;
- if (i != n - 1) {
- id[i + 3 * (n * 2 - 1)] = (n - 1) * 3 + i;
- } else {
- id[i + 3 * (n * 2 - 1)] = 0;
- }
- }
- for (int i = 0; i < n - 1; i++) {
- id[i + n] = (n - 1) * 12 + i;
- id[i + (n * 2 - 1) + n] = (n - 1) * 5 + i;
- id[i + 2 * (n * 2 - 1) + n] = (n - 1) * 2 + i;
- id[i + 3 * (n * 2 - 1) + n] = (n - 1) * 11 + i;
- }
- for (int i = 0; i < id.length; i++) {
- parents[i] = dsu.p[id[i]];
- size[i] = dsu.sz[id[i]];
- }
- HashSet<Integer> was = new HashSet<Integer>();
- was.add(-1);
- for (int i = 0; i < parents.length; i++)
- was.add(parents[i]);
- for (int i = 0; i < dsu.n; i++) {
- int x = dsu.get(i);
- if (!was.contains(x)) {
- was.add(x);
- inside++;
- }
- }
- boolean[] isOnSide = new boolean[dsu.n];
- int[] backId = new int[dsu.n];
- for (int i = 0; i < id.length; i++) {
- isOnSide[id[i]] = true;
- backId[id[i]] = i;
- }
- int[] next = new int[dsu.n];
- for (int i = 0; i < next.length; i++)
- if (isOnSide[i])
- next[i] = backId[i];
- else
- next[i] = -1;
- for (int i = 0; i < id.length; i++)
- if (parents[i] != -1)
- if (next[parents[i]] == -1) {
- size[i] = dsu.sz[parents[i]];
- next[parents[i]] = i;
- }
- for (int i = 0; i < parents.length; i++)
- if (parents[i] != -1)
- parents[i] = next[parents[i]];
- Answer ans = new Answer(parents, size, inside, n * 2);
- hm.put(name, ans);
- }
- return hm.get(name);
- }
- void solve() {
- while (true) {
- try {
- String s = in.br.readLine();
- if (s == null || s.length() == 0)
- break;
- String name = s.substring(0, s.indexOf("="));
- s = s.substring(s.indexOf("=") + 1);
- String[] all = new String[4];
- for (int it = 0; it < 4; it++) {
- int end = s.indexOf(",");
- if (end == -1)
- end = s.length();
- all[it] = s.substring(0, end);
- if (it != 3)
- s = s.substring(end + 1);
- }
- consOf.put(name, new ConsistOf(all));
- } catch (IOException e) {
- break;
- }
- }
- Answer a = getAnswer("Map");
- long ans = a.inside;
- HashSet<Integer> hs = new HashSet<Integer>();
- for (int i = 0; i < 4 * (a.length - 1); i++)
- if (a.parents[i] != -1)
- hs.add(a.parents[i]);
- ans += hs.size();
- out.println(ans);
- }
- void run() {
- try {
- in = new FastScanner(new File("map.in"));
- out = new PrintWriter(new File("map.out"));
- solve();
- out.close();
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- void runIO() {
- in = new FastScanner(System.in);
- out = new PrintWriter(System.out);
- solve();
- out.close();
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- public FastScanner(InputStream f) {
- br = new BufferedReader(new InputStreamReader(f));
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return null;
- st = new StringTokenizer(s);
- }
- return st.nextToken();
- }
- boolean hasMoreTokens() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return false;
- st = new StringTokenizer(s);
- }
- return true;
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- }
- public static void main(String[] args) {
- new Map().run();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment