| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 582491 |
2022-06-23T23:17:30 Z |
errorgorn |
Paint (COI20_paint) |
C++17 |
|
937 ms |
311836 KB |
// Super Idol的笑容
// 都没你的甜
// 八月正午的阳光
// 都没你耀眼
// 热爱105°C的你
// 滴滴清纯的蒸馏水
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int B=650;
int p[200005];
int par(int i){
if (p[i]==i) return i;
else return p[i]=par(p[i]);
}
void unions(int i,int j){
i=par(i),j=par(j);
p[i]=j;
}
int n,m,q;
vector<int> arr[200005];
int colid[200005];
int col[200005];
vector<int> al[200005];
vector<int> al2[10005][B+5]; //for big store based on color
int typ[200005];
int IDX,IDX2;
void change(int i){ //update the color change to other
if (typ[i]!=-1) return;
for (auto it:al[i]){
it=par(it);
if (typ[it]!=-1){
al2[typ[it]][colid[col[i]]].pub(i);
}
}
}
void merge(int i,int j){
i=par(i),j=par(j);
if (i==j || col[i]!=col[j]) return;
if (typ[i]==-1) swap(i,j);
p[j]=i;
if (typ[i]==-1){
for (auto it:al[j]) al[i].pub(it);
}
else if (typ[j]==-1){
for (auto it:al[j]){
it=par(it);
if (typ[it]!=-1){
al[i].pub(it);
al[it].pub(i);
}
else if (colid[col[it]]!=-1) al2[typ[i]][colid[col[it]]].pub(it);
}
}
else{
for (auto it:al[j]) al[i].pub(it);
rep(x,0,IDX) for (auto it:al2[typ[j]][x]) al2[typ[i]][x].pub(it);
}
}
int cnt[200005];
void rebuild(int i){ //change small to big and clear duplicates from al in big guys
if (typ[i]==-1 && sz(al[i])>B){
typ[i]=IDX2++;
vector<int> temp;
for (auto it:al[i]){
it=par(it);
if (typ[it]!=-1){
temp.pub(it);
if (it!=i) al[it].pub(i);
}
else if (colid[col[it]]!=-1) al2[typ[i]][colid[col[it]]].pub(it);
}
al[i]=temp;
}
if (typ[i]==-1) return;
vector<int> temp;
for (auto &it:al[i]){
it=par(it);
if (cnt[it]==0) temp.pub(it);
cnt[it]++;
}
for (auto it:al[i]) cnt[it]--;
al[i]=temp;
}
int pos[100005];
int c[100005];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>m;
rep(x,0,n){
arr[x]=vector<int>(m);
rep(y,0,m){
cin>>arr[x][y];
col[x*m+y]=arr[x][y];
}
}
cin>>q;
int a,b;
rep(x,0,q){
cin>>a>>b>>c[x];
a--,b--;
pos[x]=a*m+b;
}
IDX2=0;
rep(x,0,n*m) typ[x]=-1;
rep(x,0,n*m) p[x]=x;
rep(x,0,n) rep(y,0,m){
if (x!=n-1 && arr[x][y]==arr[x+1][y]) unions(x*m+y,(x+1)*m+y);
if (y!=m-1 && arr[x][y]==arr[x][y+1]) unions(x*m+y,x*m+(y+1));
}
rep(x,0,n) rep(y,0,m){
if (x!=n-1 && arr[x][y]!=arr[x+1][y]){
int a=par(x*m+y),b=par((x+1)*m+y);
al[a].pub(b);
al[b].pub(a);
}
if (y!=m-1 && arr[x][y]!=arr[x][y+1]){
int a=par(x*m+y),b=par(x*m+(y+1));
al[a].pub(b);
al[b].pub(a);
}
}
rep(x,0,n*m) if (p[x]==x) rebuild(x);
for (int i=0;i<q;i+=B){
IDX=0;
rep(x,0,100005) colid[x]=-1;
rep(x,i,min(q,i+B)) if (colid[c[x]]==-1) colid[c[x]]=IDX++;
rep(x,0,IDX2) rep(y,0,IDX) al2[x][y].clear();
rep(x,0,n) rep(y,0,m){
if (x!=n-1){
int a=par(x*m+y),b=par((x+1)*m+y);
if (typ[a]!=-1 && typ[b]==-1 && colid[col[b]]!=-1){
al2[typ[a]][colid[col[b]]].pub(b);
}
if (typ[b]!=-1 && typ[a]==-1 && colid[col[a]]!=-1){
al2[typ[b]][colid[col[a]]].pub(a);
}
}
if (y!=m-1){
int a=par(x*m+y),b=par(x*m+(y+1));
if (typ[a]!=-1 && typ[b]==-1 && colid[col[b]]!=-1){
al2[typ[a]][colid[col[b]]].pub(b);
}
if (typ[b]!=-1 && typ[a]==-1 && colid[col[a]]!=-1){
al2[typ[b]][colid[col[a]]].pub(a);
}
}
}
rep(x,i,min(q,i+B)){
pos[x]=par(pos[x]);
col[pos[x]]=c[x];
change(pos[x]);
vector<int> v;
for (auto it:al[pos[x]]) v.pub(it);
if (typ[pos[x]]!=-1){
for (auto it:al2[typ[pos[x]]][colid[c[x]]]) v.pub(it);
al2[typ[pos[x]]][colid[c[x]]].clear();
}
for (auto it:v) merge(pos[x],it);
rebuild(par(pos[x]));
}
}
rep(x,0,n){
rep(y,0,m) cout<<col[par(x*m+y)]<<" "; cout<<endl;
}
}
Compilation message
paint.cpp: In function 'int main()':
paint.cpp:27:26: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
27 | #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
| ^~~
paint.cpp:221:3: note: in expansion of macro 'rep'
221 | rep(y,0,m) cout<<col[par(x*m+y)]<<" "; cout<<endl;
| ^~~
paint.cpp:221:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
221 | rep(y,0,m) cout<<col[par(x*m+y)]<<" "; cout<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
164468 KB |
Output is correct |
| 2 |
Correct |
82 ms |
164548 KB |
Output is correct |
| 3 |
Correct |
84 ms |
165388 KB |
Output is correct |
| 4 |
Correct |
89 ms |
166604 KB |
Output is correct |
| 5 |
Correct |
83 ms |
165580 KB |
Output is correct |
| 6 |
Correct |
88 ms |
166484 KB |
Output is correct |
| 7 |
Correct |
92 ms |
164400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
189 ms |
171360 KB |
Output is correct |
| 2 |
Correct |
374 ms |
199060 KB |
Output is correct |
| 3 |
Correct |
319 ms |
181664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
259 ms |
208412 KB |
Output is correct |
| 2 |
Correct |
303 ms |
221768 KB |
Output is correct |
| 3 |
Correct |
276 ms |
217712 KB |
Output is correct |
| 4 |
Correct |
881 ms |
311836 KB |
Output is correct |
| 5 |
Correct |
450 ms |
264524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
405 ms |
195436 KB |
Output is correct |
| 2 |
Correct |
705 ms |
185836 KB |
Output is correct |
| 3 |
Correct |
757 ms |
208348 KB |
Output is correct |
| 4 |
Correct |
635 ms |
183116 KB |
Output is correct |
| 5 |
Correct |
900 ms |
227280 KB |
Output is correct |
| 6 |
Correct |
493 ms |
181604 KB |
Output is correct |
| 7 |
Correct |
560 ms |
180232 KB |
Output is correct |
| 8 |
Correct |
581 ms |
179264 KB |
Output is correct |
| 9 |
Correct |
937 ms |
229308 KB |
Output is correct |
