#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 2e5 + 7;
const int cx = 1e5 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int block = 600;
int par[MAXN], col[MAXN], n, m;
vi pop[MAXN], adj[MAXN];
vector<set<int>> sus[MAXN];
set<int> vel;
bool bg[MAXN], unutar[MAXN];
void merge(int a, int b){
if(pop[a].size() < pop[b].size()) swap(a, b);
if(pop[a].size() < block and pop[a].size() + pop[b].size() >= block){
sus[a].resize(cx);
vel.insert(a);
bg[a] = 1;
for(int x : adj[a]){
x = par[x];
sus[a][col[x]].insert(x);
}
}
if(pop[a].size() + pop[b].size() >= block){
for(int x : adj[b]){
x = par[x];
if(x != a) sus[a][col[x]].insert(x);
}
if(bg[b]){
sus[b].clear();
sus[b].shrink_to_fit();
vel.erase(b);
bg[b] = 0;
}
}
for(int x : pop[b]) pop[a].PB(x), par[x] = a;
for(int x : adj[b]) adj[a].PB(x);
adj[b].clear();
adj[b].shrink_to_fit();
pop[b].clear();
adj[b].shrink_to_fit();
}
void prin(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++) cout << col[par[i * m + j]] << " ";
cout << "\n";
}
}
void bojaj(int a, int c){
a = par[a];
col[a] = c;
while(1){
if(!bg[a]){
bool naso = 0;
for(int x : adj[a]){
x = par[x];
if(a != x and col[x] == c){
merge(a, x);
a = par[a];
naso = 1;
break;
}
}
if(!naso) break;
}else{
if(sus[a][c].empty()) break;
int x = *sus[a][c].begin();
sus[a][c].erase(x);
x = par[x];
if(a != x and col[x] == c){
merge(a, x);
a = par[a];
}
}
}
if(!bg[a]){
vi novi;
for(int x : adj[a]){
x = par[x];
if(x != a and !unutar[x]){
unutar[x] = 1;
novi.PB(x);
}
}
adj[a] = novi;
for(int x : vel) if(unutar[x]) sus[x][c].insert(a);
for(int x : novi) unutar[x] = 0;
}else{
for(int x : vel){
x = par[x];
if(a != x and sus[a][col[x]].count(x)) sus[x][c].insert(a);
}
}
}
void solve(){
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
int x;
cin >> x;
int cr = i * m + j;
col[cr] = x;
pop[cr].PB(cr);
par[cr] = cr;
for(int k=0; k<4; k++){
int ni = i + dx[k], nj = j + dy[k];
if(ni < 0 or ni >= n or nj < 0 or nj >= m) continue;
int nc = ni * m + nj;
adj[cr].PB(nc);
}
}
}
for(int i=0; i<n*m; i++) bojaj(i, col[i]);
int q;
cin >> q;
while(q--){
int r, s, c;
cin >> r >> s >> c;
r--, s--;
bojaj(r * m + s, c);
//prin();
}
prin();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> tt;
while(tt--) solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
14684 KB |
Output is correct |
2 |
Correct |
5 ms |
14940 KB |
Output is correct |
3 |
Correct |
8 ms |
15596 KB |
Output is correct |
4 |
Correct |
12 ms |
20148 KB |
Output is correct |
5 |
Correct |
12 ms |
20572 KB |
Output is correct |
6 |
Correct |
22 ms |
25148 KB |
Output is correct |
7 |
Correct |
3 ms |
14684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
19560 KB |
Output is correct |
2 |
Correct |
192 ms |
216792 KB |
Output is correct |
3 |
Correct |
92 ms |
39184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
145 ms |
51292 KB |
Output is correct |
2 |
Correct |
156 ms |
56516 KB |
Output is correct |
3 |
Correct |
163 ms |
73728 KB |
Output is correct |
4 |
Correct |
201 ms |
130600 KB |
Output is correct |
5 |
Correct |
171 ms |
161760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
42068 KB |
Output is correct |
2 |
Correct |
249 ms |
49124 KB |
Output is correct |
3 |
Correct |
473 ms |
222440 KB |
Output is correct |
4 |
Correct |
624 ms |
456020 KB |
Output is correct |
5 |
Correct |
279 ms |
126180 KB |
Output is correct |
6 |
Correct |
321 ms |
160848 KB |
Output is correct |
7 |
Correct |
242 ms |
123832 KB |
Output is correct |
8 |
Correct |
179 ms |
95908 KB |
Output is correct |
9 |
Correct |
235 ms |
45376 KB |
Output is correct |