Submission #1003908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003908		vjudge1	Paint (COI20_paint)	C++14	0 / 100	131 ms	49232 KiB

paint

#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, m));
    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(); rep = find(rep); }
  }

  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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52