oj.uz

Submission #950084

# Submission time Handle Problem Language Result Execution time Memory
950084 2024-03-20T05:04:10 Z NeroZein Paint (COI20_paint) C++17
0 / 100
 310 ms 288336 KB 
#include "bits/stdc++.h"
using namespace std;

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

const int B = 1e5;
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.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 27228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 88116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 212 ms 203316 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 288336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -