oj.uz

Submission #1004318

# Submission time Handle Problem Language Result Execution time Memory
1004318 2024-06-21T07:38:46 Z vjudge1 Paint (COI20_paint) C++17
0 / 100
 41 ms 2128 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+5;

int mi[N], mx[N], par[N], color[N];

int root(int x)
{
  if(par[x] == x) return x;
  return par[x] = root(par[x]);
}

void merge(int a, int b)
{
  a = root(a), b = root(b);
  if(a == b) return;
  
  par[a] = b;
  mi[b] = min(mi[a], mi[b]);
  mx[b] = max(mx[a], mx[b]);
}

int main()
{
  int r, c;
  cin >> r >> c;

  for(int i = 0; i < c; i ++)
    mx[i] = mi[i] = par[i] = i;
  
  int a[r][c];

  for(int i = 0; i < r; i ++)
    for(int j = 0; j < c; j ++)
      {
	cin >> a[i][j];
	color[j] = a[i][j];
      }

  int q;
  cin >> q;
  while(q--)
    {
      int i, j, col;
      cin >> i >> j >> col;
      j--;
      i = root(j);

      color[i] = col;
      if(mx[i] + 1 < c && color[root(mx[i] + 1)] == col)
	merge(i, mx[i] + 1);

      if(mi[i] > 0 && color[root(mi[i] - 1)] == col)
	merge(i, mi[i] - 1);
    }

  for(int i = 0; i < c; i ++)
    cout << color[root(i)] << ' ';
  cout << endl;
  return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 2128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -