| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577432 |
2022-06-14T18:09:40 Z |
czhang2718 |
Paint (COI20_paint) |
C++17 |
|
119 ms |
25424 KB |
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second
#define pb push_back
#define nl '\n'
#define sz(x) (int) x.size()
#define rep(i,a,b) for(int i=a; i<=b; i++)
const int N=200000;
const int B=400;
int r, c, q;
vector<vi> g;
int par[N];
int sz[N];
int col[N];
vi adj[N];
vi big;
map<int, set<int>> adj2[N];
int dx[]={-1, 0, 0, 1};
int dy[]={0, -1, 1, 0};
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
void join(int x, int y){
// cout << "join " << x << " " << y << nl;
int a=find(x);
int b=find(y);
if(a==b) return;
// cout << "ab " << a << " " << b << nl;
if(sz[b]>sz[a]) swap(a,b);
if(sz[a]>B && sz[b]>B){
for(auto e:adj2[b]){
for(int k:e.s) adj2[a][e.f].insert(k); // shouldn't need find(k)
}
}
else if(sz[a]>B && sz[b]<=B){
for(int k:adj[b]){
// k=find(k);
// int c=col[k];
// if(k!=a && k!=b) adj2[a][c].insert(k);
int c=col[find(k)];
if(k!=a && k!=b) adj2[a][c].insert(find(k));
}
}
else if(sz[a]+sz[b]<=B) {
for(int k:adj[b]) if(find(k)!=a && find(k)!=b) adj[a].pb(k);
}
if(sz[a]+sz[b]>B && sz[a]<=B){
big.pb(a);
for(int k:adj[a]) if(find(k)!=a && find(k)!=b) adj2[a][col[find(k)]].insert(find(k));
}
par[b]=a;
sz[a]+=sz[b];
}
int h(int i, int j){
return c*i+j;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> r >> c;
g.resize(r, vi(c));
rep(i,0,r-1){
rep(j,0,c-1){
par[h(i,j)]=h(i,j);
sz[h(i,j)]=1;
rep(k,0,1){
int x=i+dx[k];
int y=j+dy[k];
if(x<0 || y<0) continue;
adj[h(i,j)].pb(h(x,y));
adj[h(x,y)].pb(h(i,j));
}
}
}
rep(i,0,r-1){
rep(j,0,c-1){
cin >> g[i][j];
col[h(i,j)]=g[i][j];
rep(k,0,1){
int x=i+dx[k];
int y=j+dy[k];
if(x<0 || y<0) continue;
if(g[i][j]==g[x][y]) join(h(i,j), h(x,y));
}
}
}
cin >> q;
while(q--){
int x, y, c;
cin >> x >> y >> c;
x--; y--;
int i=find(h(x,y));
col[i]=c;
if(sz[i]>B){
vi nei;
for(int p:adj2[i][c]) nei.pb(p);
adj2[i][c].clear();
for(int k:nei) if(col[find(k)]==c) join(i, k);
}
else{
vi nei;
for(int p:adj[i]) nei.pb(p);
for(int k:nei){
if(col[find(k)]==c) join(i, k);
}
}
i=find(i);
if(sz[i]<=B){
// assert(adj[i].size()<=4*sz[i]);
for(int k:adj[i]){
k=find(k);
if(sz[k]>B && k!=i) adj2[k][c].insert(i);
}
}
else{
// assert(big.size()<=r*c/B);
for(int j:big){
j=find(j);
if(j==i) continue;
if(adj2[i][col[j]].find(j)!=adj2[i][col[j]].end()) adj2[j][c].insert(i);
}
}
}
rep(i,0,r-1){
rep(j,0,c-1){
cout << col[find(h(i,j))] << " ";
}
cout << nl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
11 ms |
14920 KB |
Output is correct |
| 4 |
Correct |
13 ms |
14920 KB |
Output is correct |
| 5 |
Incorrect |
25 ms |
16216 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
16904 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
19968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
25100 KB |
Output is correct |
| 2 |
Incorrect |
114 ms |
25424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
23704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
