Advertisement
ATSTNG

Problem 7 / Both heuristics

Nov 19th, 2018
276
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 14.26 KB | None | 0 0
  1. import java.io.OutputStream;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.OutputStream;
  5. import java.io.PrintWriter;
  6. import java.util.Arrays;
  7. import java.io.BufferedWriter;
  8. import java.util.InputMismatchException;
  9. import java.io.IOException;
  10. import java.util.ArrayList;
  11. import java.util.List;
  12. import java.io.Writer;
  13. import java.io.OutputStreamWriter;
  14. import java.io.InputStream;
  15.  
  16. /**
  17.  * Built using CHelper plug-in
  18.  * Actual solution is at the top
  19.  *
  20.  * @author Rustam Musin (t.me/musin_acm)
  21.  */
  22. public class Main {
  23.     public static void main(String[] args) {
  24.         InputStream inputStream = System.in;
  25.         OutputStream outputStream = System.out;
  26.         InputReader in = new InputReader(inputStream);
  27.         OutputWriter out = new OutputWriter(outputStream);
  28.         Task7 solver = new Task7();
  29.         solver.solve(1, in, out);
  30.         out.close();
  31.     }
  32.  
  33.     static class Task7 {
  34.         IntIntPair[] a;
  35.         int n;
  36.         int[][] g;
  37.         Query[] queries;
  38.  
  39.         public void solve(int testNumber, InputReader in, OutputWriter out) {
  40.             readInput(in);
  41.             new Solver().solve();
  42.             for (Query q : queries) {
  43.                 out.printLine(q.fail ? "fail" : "ok");
  44.             }
  45.         }
  46.  
  47.         int find(IntIntPair[] a, IntIntPair p) {
  48.             return Arrays.binarySearch(a, p);
  49.         }
  50.  
  51.         void readInput(InputReader in) {
  52.             n = in.readInt();
  53.             a = new IntIntPair[n];
  54.             for (int i = 0; i < n; i++) {
  55.                 a[i] = IntIntPair.makePair(in.readInt(), in.readInt());
  56.             }
  57.             Arrays.sort(a);
  58.             int[] size = new int[n];
  59.             int[] dx = {-1, 0, 1, 0};
  60.             int[] dy = {0, 1, 0, -1};
  61.             for (IntIntPair p : a) {
  62.                 int cur = find(a, p);
  63.                 for (int d = 0; d < 4; d++) {
  64.                     int x = p.first + dx[d];
  65.                     int y = p.second + dy[d];
  66.                     int id = find(a, IntIntPair.makePair(x, y));
  67.                     if (id >= 0) {
  68.                         size[cur]++;
  69.                     }
  70.                 }
  71.             }
  72.             g = new int[n][];
  73.             for (int i = 0; i < n; i++) {
  74.                 g[i] = new int[size[i]];
  75.             }
  76.             for (IntIntPair p : a) {
  77.                 int cur = find(a, p);
  78.                 for (int d = 0; d < 4; d++) {
  79.                     int x = p.first + dx[d];
  80.                     int y = p.second + dy[d];
  81.                     int id = find(a, IntIntPair.makePair(x, y));
  82.                     if (id >= 0) {
  83.                         g[cur][--size[cur]] = id;
  84.                     }
  85.                 }
  86.             }
  87.             int queryCount = in.readInt();
  88.             queries = new Query[queryCount];
  89.             for (int i = 0; i < queryCount; i++) {
  90.                 int monsterCount = in.readInt();
  91.                 int weaponCount = in.readInt();
  92.                 int player = find(a, IntIntPair.makePair(in.readInt(), in.readInt()));
  93.                 int[] monsters = new int[monsterCount];
  94.                 for (int j = 0; j < monsterCount; j++) {
  95.                     monsters[j] = find(a, IntIntPair.makePair(in.readInt(), in.readInt()));
  96.                 }
  97.                 int[] weapons = new int[weaponCount];
  98.                 for (int j = 0; j < weaponCount; j++) {
  99.                     weapons[j] = find(a, IntIntPair.makePair(in.readInt(), in.readInt()));
  100.                 }
  101.                 queries[i] = new Query(i, player, weapons, monsters);
  102.             }
  103.         }
  104.  
  105.         class Solver {
  106.             List<Integer>[] tree;
  107.             int treeN;
  108.             boolean[] isActive;
  109.             List<Integer> notRemoved;
  110.             DSU dsu;
  111.  
  112.             void solve() {
  113.                 buildTree();
  114.                 dsu = new DSU();
  115.                 isActive = new boolean[n];
  116.                 notRemoved = new ArrayList<>();
  117.                 for (int i = 0; i < n; i++) {
  118.                     notRemoved.add(i);
  119.                 }
  120.                 dfs(1);
  121.             }
  122.  
  123.             void buildTree() {
  124.                 int log = 1;
  125.                 while (1 << log < queries.length) {
  126.                     log++;
  127.                 }
  128.                 treeN = 1 << log;
  129.                 tree = new List[2 * treeN];
  130.                 for (int i = 0; i < tree.length; i++) {
  131.                     tree[i] = new ArrayList<>();
  132.                 }
  133.                 for (int i = 0; i < queries.length; i++) {
  134.                     for (int w : queries[i].weapons) {
  135.                         tree[i + treeN].add(w);
  136.                     }
  137.                 }
  138.                 for (int i = treeN - 1; i > 0; i--) {
  139.                     List<Integer> both = new ArrayList<>();
  140.                     int leftAt = 0;
  141.                     int rightAt = 0;
  142.                     List<Integer> leftCh = tree[i * 2];
  143.                     List<Integer> rightCh = tree[i * 2 + 1];
  144.                     while (leftAt < leftCh.size() && rightAt < rightCh.size()) {
  145.                         if (leftCh.get(leftAt) == (int) rightCh.get(rightAt)) {
  146.                             both.add(leftCh.get(leftAt));
  147.                             leftAt++;
  148.                             rightAt++;
  149.                         } else if (leftCh.get(leftAt) < rightCh.get(rightAt)) {
  150.                             both.add(leftCh.get(leftAt++));
  151.                         } else {
  152.                             both.add(rightCh.get(rightAt++));
  153.                         }
  154.                     }
  155.                     while (leftAt < leftCh.size()) {
  156.                         both.add(leftCh.get(leftAt++));
  157.                     }
  158.                     while (rightAt < rightCh.size()) {
  159.                         both.add(rightCh.get(rightAt++));
  160.                     }
  161.                     tree[i] = both;
  162.                 }
  163.             }
  164.  
  165.             void dfs(int v) {
  166.                 int startActions = dsu.actions.size();
  167.                 List<Integer> newNotRemoved = new ArrayList<>();
  168.                 List<Integer> removed = new ArrayList<>();
  169.                 int at = 0;
  170.                 for (int x : notRemoved) {
  171.                     while (at < tree[v].size() && tree[v].get(at) < x) {
  172.                         at++;
  173.                     }
  174.                     if (at < tree[v].size() && tree[v].get(at) == x) {
  175.                         newNotRemoved.add(x);
  176.                     } else {
  177.                         isActive[x] = true;
  178.                         for (int to : g[x]) {
  179.                             if (isActive[to]) {
  180.                                 dsu.unite(x, to);
  181.                             }
  182.                         }
  183.                         removed.add(x);
  184.                     }
  185.                 }
  186.                 if (v < treeN) {
  187.                     List<Integer> old = notRemoved;
  188.                     notRemoved = newNotRemoved;
  189.                     dfs(v * 2);
  190.                     dfs(v * 2 + 1);
  191.                     notRemoved = old;
  192.                 } else {
  193.                     if (v - treeN < queries.length) {
  194.                         Query query = queries[v - treeN];
  195.                         for (int monster : query.monsters) {
  196.                             query.fail |= dsu.find(query.player) == dsu.find(monster);
  197.                         }
  198.                     }
  199.                 }
  200.                 for (int x : removed) {
  201.                     isActive[x] = false;
  202.                 }
  203.                 dsu.restore(startActions);
  204.             }
  205.  
  206.         }
  207.  
  208.         class Query {
  209.             int index;
  210.             int player;
  211.             int[] weapons;
  212.             int[] monsters;
  213.             boolean fail;
  214.  
  215.             Query(int index, int player, int[] weapons, int[] monsters) {
  216.                 this.index = index;
  217.                 this.player = player;
  218.                 this.weapons = weapons;
  219.                 this.monsters = monsters;
  220.                 Arrays.sort(weapons);
  221.                 Arrays.sort(monsters);
  222.             }
  223.  
  224.         }
  225.  
  226.         enum ActionType {
  227.             PARENT,
  228.             RANK,
  229.             ;
  230.         }
  231.  
  232.         class Action {
  233.             Task7.ActionType type;
  234.             int index;
  235.             int value;
  236.  
  237.             Action(Task7.ActionType type, int index, int value) {
  238.                 this.type = type;
  239.                 this.index = index;
  240.                 this.value = value;
  241.             }
  242.  
  243.         }
  244.  
  245.         class DSU {
  246.             int[] parent;
  247.             int[] rank;
  248.             List<Action> actions = new ArrayList<>();
  249.  
  250.             DSU() {
  251.                 parent = new int[n];
  252.                 rank = new int[n];
  253.                 for (int i = 0; i < n; i++) {
  254.                     parent[i] = i;
  255.                     rank[i] = 1;
  256.                 }
  257.             }
  258.  
  259.             void saveChange(boolean parent, int index, int value) {
  260.                 if (parent) {
  261.                     actions.add(new Action(Task7.ActionType.PARENT, index, value));
  262.                 } else {
  263.                     actions.add(new Action(Task7.ActionType.RANK, index, value));
  264.                 }
  265.             }
  266.  
  267.             int find(int v) {
  268.                 if (parent[v] == v) {
  269.                     return v;
  270.                 }
  271.                 saveChange(true, v, parent[v]);
  272.                 return parent[v] = find(parent[v]);
  273.             }
  274.  
  275.             boolean unite(int u, int v) {
  276.                 u = find(u);
  277.                 v = find(v);
  278.                 if (u == v) {
  279.                     return false;
  280.                 }
  281.                 if (rank[u] > rank[v]) {
  282.                     return unite(v, u);
  283.                 }
  284.                 saveChange(true, u, parent[u]);
  285.                 saveChange(false, v, rank[v]);
  286.                 parent[u] = v;
  287.                 rank[v] = Math.max(rank[v], rank[u] + 1);
  288.                 return true;
  289.             }
  290.  
  291.             void restore(int leftActions) {
  292.                 while (actions.size() > leftActions) {
  293.                     Action action = actions.get(actions.size() - 1);
  294.                     actions.remove(actions.size() - 1);
  295.                     if (action.type == Task7.ActionType.PARENT) {
  296.                         parent[action.index] = action.value;
  297.                     } else {
  298.                         rank[action.index] = action.value;
  299.                     }
  300.                 }
  301.             }
  302.  
  303.         }
  304.  
  305.     }
  306.  
  307.     static class IntIntPair implements Comparable<IntIntPair> {
  308.         public final int first;
  309.         public final int second;
  310.  
  311.         public static IntIntPair makePair(int first, int second) {
  312.             return new IntIntPair(first, second);
  313.         }
  314.  
  315.         public IntIntPair(int first, int second) {
  316.             this.first = first;
  317.             this.second = second;
  318.         }
  319.  
  320.         public boolean equals(Object o) {
  321.             if (this == o) {
  322.                 return true;
  323.             }
  324.             if (o == null || getClass() != o.getClass()) {
  325.                 return false;
  326.             }
  327.  
  328.             IntIntPair pair = (IntIntPair) o;
  329.  
  330.             return first == pair.first && second == pair.second;
  331.         }
  332.  
  333.         public int hashCode() {
  334.             int result = first;
  335.             result = 31 * result + second;
  336.             return result;
  337.         }
  338.  
  339.         public String toString() {
  340.             return "(" + first + "," + second + ")";
  341.         }
  342.  
  343.         public int compareTo(IntIntPair o) {
  344.             int value = Integer.compare(first, o.first);
  345.             if (value != 0) {
  346.                 return value;
  347.             }
  348.             return Integer.compare(second, o.second);
  349.         }
  350.  
  351.     }
  352.  
  353.     static class OutputWriter {
  354.         private final PrintWriter writer;
  355.  
  356.         public OutputWriter(OutputStream outputStream) {
  357.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  358.         }
  359.  
  360.         public OutputWriter(Writer writer) {
  361.             this.writer = new PrintWriter(writer);
  362.         }
  363.  
  364.         public void print(Object... objects) {
  365.             for (int i = 0; i < objects.length; i++) {
  366.                 if (i != 0) {
  367.                     writer.print(' ');
  368.                 }
  369.                 writer.print(objects[i]);
  370.             }
  371.         }
  372.  
  373.         public void printLine(Object... objects) {
  374.             print(objects);
  375.             writer.println();
  376.         }
  377.  
  378.         public void close() {
  379.             writer.close();
  380.         }
  381.  
  382.     }
  383.  
  384.     static class InputReader {
  385.         private InputStream stream;
  386.         private byte[] buf = new byte[1024];
  387.         private int curChar;
  388.         private int numChars;
  389.         private InputReader.SpaceCharFilter filter;
  390.  
  391.         public InputReader(InputStream stream) {
  392.             this.stream = stream;
  393.         }
  394.  
  395.         public int read() {
  396.             if (numChars == -1) {
  397.                 throw new InputMismatchException();
  398.             }
  399.             if (curChar >= numChars) {
  400.                 curChar = 0;
  401.                 try {
  402.                     numChars = stream.read(buf);
  403.                 } catch (IOException e) {
  404.                     throw new InputMismatchException();
  405.                 }
  406.                 if (numChars <= 0) {
  407.                     return -1;
  408.                 }
  409.             }
  410.             return buf[curChar++];
  411.         }
  412.  
  413.         public int readInt() {
  414.             int c = read();
  415.             while (isSpaceChar(c)) {
  416.                 c = read();
  417.             }
  418.             int sgn = 1;
  419.             if (c == '-') {
  420.                 sgn = -1;
  421.                 c = read();
  422.             }
  423.             int res = 0;
  424.             do {
  425.                 if (c < '0' || c > '9') {
  426.                     throw new InputMismatchException();
  427.                 }
  428.                 res *= 10;
  429.                 res += c - '0';
  430.                 c = read();
  431.             } while (!isSpaceChar(c));
  432.             return res * sgn;
  433.         }
  434.  
  435.         public boolean isSpaceChar(int c) {
  436.             if (filter != null) {
  437.                 return filter.isSpaceChar(c);
  438.             }
  439.             return isWhitespace(c);
  440.         }
  441.  
  442.         public static boolean isWhitespace(int c) {
  443.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  444.         }
  445.  
  446.         public interface SpaceCharFilter {
  447.             public boolean isSpaceChar(int ch);
  448.  
  449.         }
  450.  
  451.     }
  452. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement