Submission #582491

#	Time	Username	Problem	Language	Result	Execution time	Memory
582491		errorgorn	Paint (COI20_paint)	C++17	100 / 100	937 ms	311836 KiB

paint

// 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 (stderr)

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;
      |                                          ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 31 / 31
• Subtask 4: 52 / 52