Submission #594839

#	Time	Username	Problem	Language	Result	Execution time	Memory
594839		lunchbox	Mars (APIO22_mars)	C++17	0 / 100	1 ms	220 KiB

mars

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

struct dsu {
  vector<int> ds;

  dsu() {}
  dsu(int n) {
    ds.assign(n, -1);
  }
  const int& operator[](int i) {
    return ds[i];
  }
  int find(int i) {
    return ds[i] < 0 ? i : ds[i] = find(ds[i]);
  }
  int size(int i) {
    return -ds[find(i)];
  }
  bool same(int i, int j) {
    return find(i) == find(j);
  }
  bool join(int i, int j) {
    i = find(i), j = find(j);
    if (i == j)
      return false;
    if (ds[i] > ds[j])
      swap(i, j);
    ds[i] += ds[j], ds[j] = i;
    return true;
  }
};

const int N = 20 * 2 + 1;

string process(vector<vector<string>> ss, int i, int j, int k, int n) {
  static int on[N][N];
  int n_ = (k + 1) * 2 + 1;
  if (k == 0)
    for (int x1 = 0; x1 < 3; x1++)
      for (int y1 = 0; y1 < 3; y1++)
        on[i + x1][j + y1] = ss[x1][y1][0] - '0';
  if (k < n - 1)
    return string(100, '0');
  else {
    dsu ds(n_ * n_);
    int m;
    for (int x = 0; x < n_; x++)
      for (int y = 0; y < n_; y++)
        if (on[x][y]) {
          if (x > 0 && on[x - 1][y])
            ds.join(x * n_ + y, (x - 1) * n_ + y);
          if (y > 0 && on[x][y - 1])
            ds.join(x * n_ + y, x * n_ + (y - 1));
        }
    m = 0;
    for (int i = 0; i < n_ * n_; i++)
      if (ds[i] < 0 && on[i / n_][i % n_])
        m++;
    string t(100, '0');
    for (int b = 0; b < 10; b++)
      t[b] = '0' + (m >> b & 1);
    return t;
  }
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 7
• Subtask 6: 0 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11