oj.uz

Submission #1003889

# Submission time Handle Problem Language Result Execution time Memory
1003889 2024-06-20T19:38:09 Z vjudge1 Paint (COI20_paint) C++14
0 / 100
 14 ms 22620 KB 
#include <bits/stdc++.h>
using namespace std;


const int maxn = 2e5 + 10;

vector<int> pai( maxn ), cor( maxn );
set<int> edges[maxn];

int id( int i, int j, int m ){ return (i - 1)*m + j; }

int find( int a ){ return (( a == pai[a] ) ? a : pai[a] = find(pai[a])); }
void join( int a, int b ){
  a = find(a); b = find(b);
  if( a == b ) return;
  if( edges[a].size() < edges[b].size() ) swap( a, b );
  pai[b] = a;
  for( int x : edges[b] ) edges[a].insert(x);
}


int main(){
  int n, m; cin >> n >> m;
  for( int i = 1; i <= n; i++ ){
    for( int j = 1; j <= m; j++ ){
      cin >> cor[id(i, j, m)];
      pai[id(i, j, m)] = id(i,j, m);
      if( i > 1 ){
        if( cor[id(i, j, m)] == cor[id(i - 1, j, m )] ){
          join( id(i, j, m), id(i - 1, j, m ) );
        }
        else{
          edges[id(i, j, m)].insert(id(i - 1, j, m ));
          edges[id(i - 1, j, m)].insert(id(i, j, m));
        }
      }

      if( j > 1 ){
        if( cor[id(i, j, m)] == cor[id(i - 1, j, m )] ){
          join( id(i, j, m), id(i - 1, j, m ) );
        }
        else{
          edges[id(i, j, m)].insert(id(i, j - 1, m ));
          edges[id(i, j - 1, m)].insert(id(i, j, m));
        }
      }
    }
  }

  int q; cin >> q;
  while( q-- ){
    int i, j, c; cin >> i >> j >> c;
    int rep = find(id(i, j, c));
    cor[rep] = c;
    for( auto it = edges[rep].begin(); it != edges[rep].end(); ){
      if( find(*it) == rep || cor[find(*it)] == cor[rep] ){
        join(*it, rep);
        it = edges[rep].erase(it);
      }
      else it++;
    }
  }

  for( int i = 1; i <= n; i++ ){
    for( int j = 1; j <= m; j++ ) cout << cor[find(id(i, j, m))] << " ";
    cout << endl;
  }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 22616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 22620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 22616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 22620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -