Submission #328732

#	Time	Username	Problem	Language	Result	Execution time	Memory
328732		MiricaMatei	Paint (COI20_paint)	C++14	8 / 100	3077 ms	96364 KiB

paint

///6.45
#include <bits/stdc++.h>

using namespace std;

const int MAXD = 200005;
const int MAXS = 400;

int col[MAXD], sz[MAXD], t[MAXD];

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

set<int>ngh[MAXD];
set<pair<int, int> >G[MAXD];
set<int>large;

void dfs(int x, int y, int ind) {
  sz[ind]++;
  a[x][y] = 0;
  comp[x][y] = ind;
  for (int i = 0; i < 4; ++i) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (a[nx][ny] == col[ind])
      dfs(nx, ny, ind);
  }
}

int f(int x) {
  if (x == t[x])
    return x;
  t[x] = f(t[x]);
  return t[x];
}

void tryJoin(int& a, int b) {
  if (a == b || col[a] != col[b] || ngh[a].find(b) == ngh[a].end())
    return ;
  if (ngh[a].size() < ngh[b].size())
    swap(a, b);
  large.erase(b);
  G[b].erase({col[a], a});
  G[a].erase({col[b], b});
  for (auto it:G[b]) {
    G[a].insert(it);
    G[it.second].erase({col[b], b});
    G[it.second].insert({col[b], a});
  }
  G[a].erase({col[a], a});
  G[b].clear();
  ngh[a].erase(b);
  ngh[b].erase(a);
  assert(ngh[a].size() >= ngh[b].size());
  for (auto it:ngh[b]) {
    ngh[a].insert(it);
    ngh[it].erase(b);
    ngh[it].insert(a);
  }
  ngh[b].clear();
  sz[a] += b;
  t[b] = a;
}

void update(int x, int y, int c) {
  int cp = f(comp[x][y]);
  if (col[cp] == c)
    return ;
  if (sz[cp] <= MAXS) {
    for (auto it:G[cp]) {
      G[it.second].erase({col[cp], cp});
      G[it.second].insert({c, cp});
    }
  }
  set<pair<int, int> >aux = G[cp];
  set<pair<int, int> >::iterator it = aux.lower_bound({c, 0});
  col[cp] = c;
  while (it != aux.end() && (*it).first == c) {
    tryJoin(cp, f((*it).second));
    it++;
  }
  set<int>aux1 = large;
  large.erase(cp);
  for (auto it:aux1)
    tryJoin(cp, f(it));
  if (sz[cp] > MAXS)
    large.insert(cp);

}

int main() {

  int n, m;
  scanf("%d%d", &n, &m);
  a = new int*[n + 5];
  comp = new int*[n + 5];
  for (int i = 0; i <= n + 3; ++i) {
    a[i] = new int[m + 5];
    comp[i] = new int[m + 5];
    for (int j = 0; j <= m + 3; ++j)
      a[i][j] = comp[i][j] = 0;
  }

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      scanf("%d", &a[i][j]);
      a[i][j]++;
    }

  int comp_ind = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      if (a[i][j]) {
        col[++comp_ind] = a[i][j];
        dfs(i, j, comp_ind);
      }

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      for (int k = 0; k < 4; ++k) {
        int x = i + dx[k];
        int y = j + dy[k];
        if (comp[i][j] != comp[x][y] && comp[x][y] != 0) {
          G[comp[i][j]].insert({col[comp[x][y]], comp[x][y]});
          ngh[comp[i][j]].insert(comp[x][y]);
        }
      }

  for (int i = 1; i <= comp_ind; ++i) {
    t[i] = i;
    if (sz[i] >= MAXS)
      large.insert(i);
  }

  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    int x, y, c;
    scanf("%d%d%d", &x, &y, &c);
    update(x, y, c + 1);
  }


  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j)
      printf("%d ", col[f(comp[i][j])] - 1);
    printf("\n");
  }

  return 0;
}

Compilation message (stderr)

paint.cpp: In function 'int main()':
paint.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
paint.cpp:108:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |       scanf("%d", &a[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~
paint.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
paint.cpp:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |     scanf("%d%d%d", &x, &y, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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