oj.uz

Submission #331452

# Submission time Handle Problem Language Result Execution time Memory
331452 2020-11-28T14:15:00 Z MiricaMatei Paint (COI20_paint) C++14
39 / 100
 3000 ms 109532 KB 
#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);

}

const int LEN = (1 << 14);
char buff[LEN];
int ind = LEN - 1;

int i32(){
    int ans = 0;

    while(buff[ind] < '0' || buff[ind] > '9'){
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }

    while(buff[ind] >= '0' && buff[ind] <= '9'){
        ans = ans * 10 + buff[ind] - '0';
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    return ans;
}

int main() {
  int n, m;
  n = i32();
  m = i32();
  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) {
      a[i][j] = i32();
      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;
  q = i32();
  for (int i = 1; i <= q; ++i) {
    int x, y, c;
    x = i32();
    y = i32();
    c = i32();
    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 i32()':
paint.cpp:101:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  101 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
paint.cpp:109:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  109 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25708 KB Output is correct
2 Correct 17 ms 25708 KB Output is correct
3 Correct 29 ms 29548 KB Output is correct
4 Correct 45 ms 28524 KB Output is correct
5 Correct 347 ms 27628 KB Output is correct
6 Correct 40 ms 27884 KB Output is correct
7 Correct 16 ms 25324 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 38636 KB Output is correct
2 Correct 255 ms 47212 KB Output is correct
3 Execution timed out 3080 ms 68216 KB Time limit exceeded

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 109280 KB Output is correct
2 Correct 605 ms 108900 KB Output is correct
3 Correct 677 ms 109532 KB Output is correct
4 Correct 719 ms 106208 KB Output is correct
5 Correct 593 ms 101220 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 80028 KB Output is correct
2 Execution timed out 3071 ms 69728 KB Time limit exceeded
3 Halted 0 ms 0 KB -