oj.uz

Submission #1003901

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

#define bug(x) cout << #x << " " << x << endl

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, j - 1, m )] ){
          join( id(i, j, m), id(i, j - 1, 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;
  queue<int> aux;
  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] ){
        aux.push(*it);
        it = edges[rep].erase(it);
      }
      else it++;
    }
    while( !aux.empty() ){ join( rep, aux.front() ); aux.pop(); }
  }

  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 Incorrect 3 ms 11356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 52.0

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