Submission #950081

#	Time	Username	Problem	Language	Result	Execution time	Memory
950081		NeroZein	Paint (COI20_paint)	C++17	0 / 100	298 ms	288196 KiB

paint

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

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int B = 502;
const int N = 2e5 + 5;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int n, m;
int p[N];
int sz[N];
int col[N];
unordered_set<int> heavy; 
unordered_map<int, unordered_set<int>> adj[N];

int getId(int x, int y) {
  return m * x + y;
}

int get(int v) {
  return p[v] = (p[v] == v ? v : get(p[v])); 
}

void merge(int u, int v) {
  for (auto& [color, su] : adj[u]) {
    for (int w : su) {
      if (get(w) != v) {
        adj[v][color].insert(w);
      }
      if (sz[u] <= B) {
        //assert(col[u] == col[v]);
        adj[w][col[u]].erase(u);
        adj[w][col[v]].insert(v);
      }
    }
  }
}

void unite(int u, int v) {
  u = get(u); v = get(v);
  if (u == v) {
    return; 
  }
  if (sz[v] < sz[u]) swap(u, v);
  if (sz[v] > B) heavy.erase(u);
  if (sz[u] > B) heavy.erase(u);
  p[u] = v;
  merge(u, v);
  sz[v] += sz[u]; 
  if (sz[v] > B) heavy.insert(v); 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      int c;
      cin >> c;
      col[getId(i, j)] = c; 
    }
  }
  for (int i = 0; i < n * m; ++i) {
    p[i] = i;
    sz[i] = 1; 
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      int curId = getId(i, j);
      for (int k = 0; k < 4; ++k) {
        int ni = i + dx[k], nj = j + dy[k];
        if (ni < 0 || ni >= n || nj < 0 || nj >= m) {
          continue; 
        }
        int otherId = getId(ni, nj); 
        adj[curId][col[otherId]].insert(otherId);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      int v = getId(i, j);
      auto tmp = adj[v][col[v]];
      adj[v][col[v]].clear();
      for (int u : tmp) {
        unite(u, v); 
      }
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int x, y, c;
    cin >> x >> y >> c;
    --x, --y;
    int curId = getId(x, y);
    int v = get(curId);
    int oldCol = col[v];
    col[v] = c;
    if (sz[v] <= B) {
      for (auto [color, sv] : adj[v]) {
        for (int u : sv) {
          adj[u][oldCol].erase(v);
          adj[u][col[v]].insert(v);
        }
      }
    }
    auto tmp = adj[v][col[v]];
    adj[v][col[v]].clear();
    for (int u : tmp) {
      if (sz[u] > B) continue; 
      unite(u, v);
    }
    for (int u : heavy) {
      int color = col[u];
      if (color == col[v] && adj[v][col[v]].count(u)) {
        unite(u, v); 
      }
    }      
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      int curId = getId(i, j);
      cout << col[get(curId)] << ' ';
    }
    cout << '\n';
  }
  return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52