Submission #950763

#	Time	Username	Problem	Language	Result	Execution time	Memory
950763		NeroZein	Paint (COI20_paint)	C++17	0 / 100	770 ms	199152 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) {
              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(v);
      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