oj.uz

Submission #951211

# Submission time Handle Problem Language Result Execution time Memory
951211 2024-03-21T11:33:16 Z NeroZein Paint (COI20_paint) C++17
0 / 100
 445 ms 384088 KB 
#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_set<int> nei[N];
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);
        }
      }
    }
  }
  for (int w : nei[u]) {
    //assert(nei[w].count(u)); 
    nei[w].erase(u);
    nei[w].insert(v);
    nei[v].insert(w); 
  }
}
 
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); 
        nei[curId].insert(otherId);
        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);
      //for (int u : nei[v]) {
        //assert(nei[u].count(v)); 
      //}
    //}
  //}
  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) {
          //assert(get(u) == u);
          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] && nei[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 Correct 8 ms 24408 KB Output is correct
2 Runtime error 26 ms 49756 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 124 ms 126948 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 336 ms 320380 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 445 ms 384088 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -