Submission #577015

#	Time	Username	Problem	Language	Result	Execution time	Memory
577015		timmyfeng	Paint (COI20_paint)	C++17	100 / 100	700 ms	460888 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#define I insert
#define A auto
#define Z int
#define V vector
#define F(i,a) for(Z i=0;i<a;++i)
#define S(a) (Z)size(a)
const Z D[]={0,1,0,-1},N=2e5;V<Z>h[N],e[N];Z o[N],l[N];V<set<Z>> hc[N];bool in[N];Z main(){cin.tie(0)->sync_with_stdio(0);Z n,m;cin>>n>>m;F(i,n*m)cin>>o[i];F(i,n)F(j,m){Z t=i*m+j;l[t]=t;e[t].push_back(t);F(d,4){Z u=i+D[d],v=j+D[(d+1)%4];if(~u&&u<n&&~v&&v<m)h[t].push_back(u*m+v);}}set<Z>g;A no=[&](Z a){V<Z>hn;for(A b:h[a]){b=l[b];if(l[b]!=a&&!in[b]){hn.push_back(b);in[b]=1;}}swap(h[a],hn);};A up=[&](Z a){if(S(e[a])>=620)for(A b:g){if(a!=b&&hc[a][o[b]].count(b))hc[b][o[a]].I(a);}else{no(a);for(A b:g){if(in[b])hc[b][o[a]].I(a);}for(A b:h[a])in[b]=0;}};A me=[&](Z a,Z b){if(S(e[a])<S(e[b]))swap(a,b);if(S(e[a])<620&&S(e[a])+S(e[b])>=620){hc[a].resize(1e5);for(A u:h[a])hc[a][o[l[u]]].I(l[u]);g.I(a);}if(S(e[a])+S(e[b])>=620){for(A u:h[b])hc[a][o[l[u]]].I(l[u]);hc[b].clear();g.erase(b);}for(A i:e[b])l[i]=a;e[a].I(end(e[a]),begin(e[b]),end(e[b]));e[b].clear();h[a].I(end(h[a]),begin(h[b]),end(h[b]));h[b].clear();};A fi=[&](Z a,Z c){a=l[a];while(1){if((Z)e[a].size()<620){bool md=0;A ih=h[a];for(A b:ih){b=l[b];if(b!=a&&o[b]==c)md=1,me(a,b),a=l[a];}if(!md)break;}else{if(!S(hc[a][c]))break;Z b=*begin(hc[a][c]);hc[a][c].erase(b);b=l[b];if(b!=a&&o[b]==c)me(a,b),a=l[a];}}o[a]=c;up(a);};F(i,n*m)fi(i,o[i]);Z q;cin>>q;F(t,q){Z i,j,c;cin>>i>>j>>c;--i,--j;fi(i*m+j,c);}F(i,n){F(j,m){cout<<o[l[i*m+j]]<<" ";}cout<<"\n";}}

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