| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577015 |
2022-06-13T21:57:35 Z |
timmyfeng |
Paint (COI20_paint) |
C++17 |
|
700 ms |
460888 KB |
#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";}}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14552 KB |
Output is correct |
| 3 |
Correct |
14 ms |
15060 KB |
Output is correct |
| 4 |
Correct |
17 ms |
19816 KB |
Output is correct |
| 5 |
Correct |
18 ms |
20308 KB |
Output is correct |
| 6 |
Correct |
32 ms |
24940 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
18124 KB |
Output is correct |
| 2 |
Correct |
217 ms |
263116 KB |
Output is correct |
| 3 |
Correct |
124 ms |
36916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
58284 KB |
Output is correct |
| 2 |
Correct |
183 ms |
56676 KB |
Output is correct |
| 3 |
Correct |
212 ms |
92840 KB |
Output is correct |
| 4 |
Correct |
280 ms |
231232 KB |
Output is correct |
| 5 |
Correct |
239 ms |
192220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
42192 KB |
Output is correct |
| 2 |
Correct |
271 ms |
43616 KB |
Output is correct |
| 3 |
Correct |
700 ms |
327700 KB |
Output is correct |
| 4 |
Correct |
657 ms |
460888 KB |
Output is correct |
| 5 |
Correct |
391 ms |
188328 KB |
Output is correct |
| 6 |
Correct |
284 ms |
158236 KB |
Output is correct |
| 7 |
Correct |
237 ms |
121152 KB |
Output is correct |
| 8 |
Correct |
208 ms |
93476 KB |
Output is correct |
| 9 |
Correct |
313 ms |
45344 KB |
Output is correct |
