Submission #198105

#	Time	Username	Problem	Language	Result	Execution time	Memory
198105		model_code	Building Skyscrapers (CEOI19_skyscrapers)	Java	51 / 100	3660 ms	216340 KiB

skyscrapers

import java.io.*;
import java.util.*;

public class skyscrapers {
  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;
 
    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }
 
    public String next() {
      while  (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }
 
    public int nextInt() {
      return Integer.parseInt(next());
    }
 
  }

  static class Cell {
    public int x, y;

    public Cell() {}

    public Cell(int x_, int y_) {
      x = x_;
      y = y_;
    }

    static long hash_combine(long h_first, long h_second) {
      return h_first ^ (h_second + (long)0x9e3779b9 + (h_first << 6) + (h_second >> 2));
    }

    static long hash_int(long x) {
      x = ((x >> 16) ^ x) * 0x45d9f3b;
      x = ((x >> 16) ^ x) * 0x45d9f3b;
      x = (x >> 16) ^ x;
      return x;
    }

    @Override
    public int hashCode() {
      long h_first  = hash_int(x & 0xFFFFFFFFL);
      long h_second = hash_int(y & 0xFFFFFFFFL);

      return (int)hash_combine(h_first, h_second);
    }

    @Override
    public boolean equals(Object obj) {
      if (getClass() != obj.getClass()) return false;
      Cell c = (Cell)obj;
      return x == c.x && y == c.y;
    }
  }

  static class LegoSolver {
    int N, V;
    Cell[] cells, empty_cells;
    Map<Cell, Integer> cell_indices, empty_cell_indices;
    boolean[] removed;

    SortedSet<Integer> removable;
    boolean[] is_removable;

    List<Integer>[] G4;
    int[][] G8;

    void construct_graphs(boolean only_solvability) {
      int[] dx = {-1, -1, -1,  0,  1, 1, 1, 0};
      int[] dy = { 1,  0, -1, -1, -1, 0, 1, 1};

      if (!init_solvability_done) {
        for (int i = 0; i < N; i++) for (int j = 0; j < 8; j++) {
          Cell p = new Cell(cells[i].x + dx[j], cells[i].y + dy[j]);
          Integer it = cell_indices.get(p);
          int cell_id = (it == null) ? -1 : it;
          if (cell_id == -1) {
            Integer jt = empty_cell_indices.get(p);
            if (jt == null) {
              empty_cell_indices.put(p, V-N);
              cell_id = V;
              empty_cells[V-N] = p;
              G4[V] = new ArrayList<Integer>(4);
              for(int k = 0; k < 8; k++) G8[V][k] = V;
              V++;
            }
            else cell_id = N + jt;
            G8[cell_id][4^j] = i;
            if (j % 2 != 0) G4[cell_id].add(i);
          }
          G8[i][j] = cell_id;
          if (j % 2 != 0) G4[i].add(cell_id);
        }
      }
      if (!init_done && !only_solvability) {
        for (int i = 0; i < V-N; i++) for (int j = 0; j < 8; j++) {
          if (G8[N+i][j] != N+i) continue;
          Cell p = new Cell(empty_cells[i].x + dx[j], empty_cells[i].y + dy[j]);
          Integer it = empty_cell_indices.get(p);
          if (it == null) continue;
          int cell_id = N + it;
          G8[N+i][j] = cell_id;
          if (j % 2 != 0) G4[N+i].add(cell_id);
        }
      }
    }

    void construct_graphs() { construct_graphs(false); }

    int outer_component;
    List<Integer>[] components4, components8;
    int[] comp4, comp8;
    int[] deg4, deg8; // degree = number of full neighbouring cells

    void find_components(boolean only_solvability) {
      Queue<Integer> q = new LinkedList<Integer>();

      if (!init_solvability_done) {
        components4 = new ArrayList[V];
        components8 = new ArrayList[V];
        comp4 = new int[V];
        comp8 = new int[V];
        deg4 = new int[V];
        deg8 = new int[V];
        for (int i = 0; i < V; i++) {
            comp4[i] = comp8[i] = -1;
            deg4[i] = deg8[i] = 0;
        }
        for (int i = 0; i < V; i++) if (comp8[i] == -1 && !is_empty(i)) {
          comp8[i] = i;
          components8[i] = new ArrayList<Integer>(1);
          components8[i].add(i);
          q.add(i);
          while (!q.isEmpty()) {
            int u = q.remove();
            for (int v : G8[u]) if (comp8[v] == -1 && !is_empty(v)) {
              comp8[v] = i;
              components8[i].add(v);
              q.add(v);
            } 
          }
        }
      }
      if (!init_done && !only_solvability) {
        for (int i = 0; i < V; i++) if (comp4[i] == -1 && is_empty(i)) {
          comp4[i] = i;
          components4[i] = new ArrayList<Integer>(1);
          components4[i].add(i);
          q.add(i);
          while (!q.isEmpty()) {
            int u = q.remove();
            for (int v : G4[u]) if (comp4[v] == -1 && is_empty(v)) {
              comp4[v] = i;
              components4[i].add(v);
              q.add(v);
            } 
          }
        }
        for (int i = 0; i < V; i++) {
          for (int v : G4[i]) if (!is_empty(v)) deg4[i]++;
          for (int v : G8[i]) if (!is_empty(v)) deg8[i]++;
        }
      }
    }

    void find_components() { find_components(false); }

    void add_edge(int v1, int v2) {
      int c1 = comp4[v1], c2 = comp4[v2];
      if (c1 == c2) return;
      if (components4[c1].size() < components4[c2].size()) {int tmp = c1; c1 = c2; c2 = tmp;}
      for (int v : components4[c2]) {
        comp4[v] = c1;
        components4[c1].add(v);
      }
      if (c2 == outer_component) outer_component = c1;
      for (int v : components4[c2])
        for (int f : G8[v]) if (!is_empty(f)) update(f);
    }

    static byte[] seen;

    void update(int v) {

      boolean reachable = false, articulation = false;

      for (int adj : G4[v]) if (is_empty(adj))
        if (comp4[adj] == outer_component) reachable = true;

      if (deg8[v] <= 1) {
        if (reachable) {
          if (!is_removable[v]) {
            removable.add(v);
            is_removable[v] = true;
          }
        }
        else if (is_removable[v]) {
          removable.remove(v);
          is_removable[v] = false;
        }
        return;
      }

      for (int j = 0; j < 8; j++) if (is_empty(G8[v][j])) {
        if (is_empty(G8[v][(j+1)%8])) continue; // 1 cell per region
        if (j % 2 == 0 && !is_empty(G8[v][(j+7)%8])) continue; // ignore corner gaps
        int c = comp4[G8[v][j]];
        if (seen[c] >= 1) {
          articulation = true;
          break;
        }
        seen[c]++;
      }
      for (int j = 0; j < 8; j++) if (is_empty(G8[v][j]))
        seen[comp4[G8[v][j]]] = 0;

      if (reachable && !articulation) {
        if (!is_removable[v]) {
          removable.add(v);
          is_removable[v] = true;
        }
      }
      else if (is_removable[v]) {
        removable.remove(v);
        is_removable[v] = false;
      }
    }

    boolean is_empty(int cell) {
      return (cell >= N || removed[cell]);
    }

    boolean init_done, init_solvability_done;

    void init_solvability() {
      if (init_solvability_done) return;
      construct_graphs(true);
      removed = new boolean[V];
      seen = new byte[V];
      for (int i = 0; i < V; i++) {
        seen[i] = 0;
        removed[i] = false;
      }
      find_components(true);
      init_solvability_done = true;
    }

    void init() {
      if (init_done) return;

      construct_graphs();
      if (!init_solvability_done) {
        removed = new boolean[V];
        for (int i = 0; i < V; i++) removed[i] = false;
      }

      find_components();
      int min_coord = cells[0].x;
      for (int i = N; i < V; i++) if (min_coord >= empty_cells[i-N].x) {
        min_coord = empty_cells[i-N].x;
        outer_component = comp4[i];
      }

      is_removable = new boolean[N];
      removable = new TreeSet<Integer>();
      for (int i = 0; i < N; i++) {
        is_removable[i] = false;
        update(i);
      }
      
      init_done = init_solvability_done = true;
    }

    public LegoSolver(List<Cell> cells_) {
      N = cells_.size();
      cells = new Cell[N];
      empty_cells = new Cell[8*N];
      cell_indices = new HashMap<Cell, Integer>(N);
      empty_cell_indices = new HashMap<Cell, Integer>(8*N);
      for (int i = 0; i < N; i++) {
        cells[i] = cells_.get(i);
        cell_indices.put(cells[i], i);
      }
      G4 = new ArrayList[9*N];
      G8 = new int[9*N][8];
      V = N;
      for (int i = 0; i < N; i++) {
        G4[i] = new ArrayList<Integer>(4);
      }
      
      init_done = init_solvability_done = false;
    }
    
    public boolean solvable() {
      init_solvability();
      return (components8[comp8[0]].size() == N);
    }

    public int remove() {
      init();
      if (removable.isEmpty()) return -1;
      int rm_id = removable.last();

      removable.remove(rm_id);
      removed[rm_id] = true;

      components4[rm_id] = new ArrayList<Integer>(1);
      components4[rm_id].add(rm_id);
      comp4[rm_id] = rm_id;
      for (int f : G4[rm_id]) if (!is_empty(f)) update(f);
      for (int v : G4[rm_id]) {
        if (is_empty(v)) add_edge(rm_id, v);
        else deg4[v]--;
      }
      for (int v : G8[rm_id]) {
        deg8[v]--;
        if (!is_empty(v)) update(v);
      }

      return rm_id;
    }
  }

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);

    int N = in.nextInt();
    int t = in.nextInt();
    List<Cell> cells = new ArrayList<Cell>(N);
    for (int i = 0; i < N; i++) {
      Cell c = new Cell();
      c.x = in.nextInt();
      c.y = in.nextInt();
      cells.add(c);
    }

    LegoSolver solver = new LegoSolver(cells);

    if (!solver.solvable()) {
      out.println("NO");
      out.close();
      return;
    }

    out.println("YES");
    int[] build = new int[N];
    for (int i = 0; i < N; i++) {
      int removed_cell_id = solver.remove();
      build[i] = removed_cell_id+1;
    }
    for (int i = 0; i < N; i++) out.println(build[N-1-i]);
    out.close();
  }
}

Compilation message (stderr)

Note: skyscrapers.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19