Submission #274749

#	Time	Username	Problem	Language	Result	Execution time	Memory
274749		Haunted_Cpp	Seats (IOI18_seats)	C++17	5 / 100	4094 ms	43688 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

class DisjointSet{
private:
  vector<int> size;
  vector<int> parent;
  vector<int> min_row;
  vector<int> max_row;
  vector<int> min_column;
  vector<int> max_column;
public:
  DisjointSet(int H, int W) {
    size = parent = min_row = max_row = min_column = max_column = vector<int>(H * W + 25);
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        int idx = i * W + j;
        size[idx] = 1;
        parent[idx] = idx;
        min_row[idx] = max_row[idx] = i;
        min_column[idx] = max_column[idx] = j;
      }
    }
  }
  int root(int x) {
    if (x == parent[x]) return x;
    return parent[x] = root(parent[x]);
  }
  void join(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return;
    if (size[a] < size[b]) swap(a, b);
    size[a] += size[b];
    max_row[a] = max(max_row[a], max_row[b]);
    min_row[a] = min(min_row[a], min_row[b]);
    max_column[a] = max(max_column[a], max_column[b]);
    min_column[a] = min(min_column[a], min_column[b]);
    parent[b] = a;
  }
  int is_cute(int idx, int tamanho_total) {
    const int s = root(idx);
    if(size[s] != tamanho_total) return 0;
    const int rec = (max_row[s] - min_row[s] + 1) * (max_column[s] - min_column[s] + 1);
    return rec == tamanho_total;
  }
};

int r, c;
vector<pair<int, int>> where;
vector<vector<int>> mat;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  r = H;
  c = W;
  where.resize(r * c);
  mat = vector<vector<int>>(r, vector<int>(c));
  for (int i = 0; i < r * c; i++) {
    where[i] = {R[i], C[i]};
    mat[R[i]][C[i]] = i;
  }
}

const int dr[] = {+1, -1, +0, +0};
const int dc[] = {+0, +0, +1, -1};

int solve() {
  DisjointSet DSU(r, c);
  int res = 0;
  const int sr = where[0].first;
  const int sc = where[0].second;
  for (int i = 0; i < r * c; i++) {
    const int linha = where[i].first;
    const int coluna = where[i].second;
    for (int x = 0; x < 4; x++) {
      if (linha + dr[x] < 0 || linha + dr[x] >= r || coluna + dc[x] < 0 || coluna + dc[x] >= c) continue;
      if (mat[linha + dr[x]][coluna + dc[x]] >= i) continue;
      DSU.join(linha * c + coluna, (linha + dr[x]) * c + coluna + dc[x]); 
    }
    res += DSU.is_cute(sr * c + sc, i + 1);
  }
  return res;
}

int swap_seats(int a, int b) {
  swap(mat[where[a].first][where[a].second], mat[where[b].first][where[b].second]);
  swap(where[a], where[b]);
  return solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30