oj.uz

Submission #328708

# Submission time Handle Problem Language Result Execution time Memory
328708 2020-11-17T18:04:30 Z MiricaMatei Paint (COI20_paint) C++14
39 / 100
 3000 ms 63208 KB 
///6.45
#include <bits/stdc++.h>

using namespace std;

const int MAXD = 200005;
const int MAXS = 10000;

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<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 || G[a].find({v[b].col, b}) == G[a].end())
    return ;
  if (v[a].cells.size() < v[b].cells.size())
    swap(a, b);
  large.erase(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();
  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++;
  }
  for (auto it:large)
    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]});
      }

  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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16108 KB Output is correct
2 Correct 13 ms 16236 KB Output is correct
3 Correct 23 ms 18284 KB Output is correct
4 Correct 34 ms 17772 KB Output is correct
5 Correct 841 ms 17484 KB Output is correct
6 Correct 31 ms 17516 KB Output is correct
7 Correct 11 ms 15980 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 23788 KB Output is correct
2 Correct 204 ms 30700 KB Output is correct
3 Execution timed out 3075 ms 48548 KB Time limit exceeded

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 62756 KB Output is correct
2 Correct 422 ms 62436 KB Output is correct
3 Correct 471 ms 63208 KB Output is correct
4 Correct 506 ms 61788 KB Output is correct
5 Correct 415 ms 59488 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 45864 KB Output is correct
2 Execution timed out 3036 ms 41624 KB Time limit exceeded
3 Halted 0 ms 0 KB -