oj.uz

답안 #1003918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003918 2024-06-20T19:58:16 Z vjudge1 Paint (COI20_paint) C++14
48 / 100
 3000 ms 60904 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 ){
          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 ){

          edges[id(i, j, m)].insert(id(i, j - 1, m ));
          edges[id(i, j - 1, m)].insert(id(i, j, m));

      }
    }
  }

  for( int i = 1; i <= n; i++ ){
    for( int j = 1; j <= m; j++ ){
      if( i > 1 ){
        if( cor[find(id(i, j, m))] == cor[find(id(i - 1, j, m ))] ){
          join( id(i, j, m), id(i - 1, j, m ) );
        }
      }

      if( j > 1 ){
        if( cor[find(id(i, j, m))] == cor[find(id(i, j - 1, m ))] ){
          join( id(i, j, m), id(i, j - 1, 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(); }
  }

  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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 11356 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 7 ms 13400 KB Output is correct
4 Correct 10 ms 13148 KB Output is correct
5 Correct 55 ms 13788 KB Output is correct
6 Correct 12 ms 13916 KB Output is correct
7 Correct 2 ms 11356 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 16476 KB Output is correct
2 Correct 92 ms 23372 KB Output is correct
3 Correct 173 ms 35308 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 49748 KB Output is correct
2 Correct 144 ms 50000 KB Output is correct
3 Correct 159 ms 49488 KB Output is correct
4 Correct 162 ms 47444 KB Output is correct
5 Correct 143 ms 44536 KB Output is correct

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 45396 KB Output is correct
2 Execution timed out 3059 ms 60904 KB Time limit exceeded
3 Halted 0 ms 0 KB -