Submission #577012

#	Time	Username	Problem	Language	Result	Execution time	Memory
577012		timmyfeng	Paint (COI20_paint)	C++17	100 / 100	778 ms	460996 KiB

paint

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