Submission #328727

#	Time	Username	Problem	Language	Result	Execution time	Memory
328727		MiricaMatei	Paint (COI20_paint)	C++14	39 / 100	3087 ms	108944 KiB

paint

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

using namespace std;

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

struct Comp {
  int col;
  vector<pair<int, int> >cells;
}v[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) {
  a[x][y] = 0;
  v[ind].cells.push_back({x, y});
  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] == v[ind].col)
      dfs(nx, ny, ind);
  }
}

void tryJoin(int& a, int b) {
  if (a == b || v[a].col != v[b].col || ngh[a].find(b) == ngh[a].end())
    return ;
  if (v[a].cells.size() < v[b].cells.size())
    swap(a, b);
  large.erase(b);
  G[b].erase({v[a].col, a});
  G[a].erase({v[b].col, b});
  for (auto it:G[b]) {
    G[a].insert(it);
    G[it.second].erase({v[b].col, b});
    G[it.second].insert({v[b].col, a});
  }
  G[a].erase({v[a].col, a});
  G[b].clear();
  ngh[a].erase(b);
  ngh[b].erase(a);
  for (auto it:ngh[b]) {
    ngh[a].insert(it);
    ngh[it].erase(b);
    ngh[it].insert(a);
  }
  ngh[b].clear();
  for (auto it:v[b].cells) {
    v[a].cells.push_back(it);
    comp[it.first][it.second] = a;
  }

  v[b].cells.clear();
}

void update(int x, int y, int c) {
  int cp = comp[x][y];
  if (v[cp].col == c)
    return ;
  if (v[cp].cells.size() <= MAXS) {
    for (auto it:G[cp]) {
      G[it.second].erase({v[cp].col, 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});
  v[cp].col = c;
  while (it != aux.end() && (*it).first == c) {
    tryJoin(cp, (*it).second);
    it++;
  }
  set<int>aux1 = large;
  large.erase(cp);
  for (auto it:aux1)
    tryJoin(cp, it);
  if (v[cp].cells.size() > 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]) {
        v[++comp_ind].col = 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({v[comp[x][y]].col, comp[x][y]});
          ngh[comp[i][j]].insert(comp[x][y]);
        }
      }

  for (int i = 1; i <= comp_ind; ++i)
    if (v[i].cells.size() >= 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 <= comp_ind; ++i)
    for (auto it:v[i].cells)
      a[it.first][it.second] = v[i].col - 1;

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

  return 0;
}

Compilation message (stderr)

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

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