| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577012 |
2022-06-13T21:50:24 Z |
timmyfeng |
Paint (COI20_paint) |
C++17 |
|
778 ms |
460996 KB |
#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";}}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
10 ms |
14552 KB |
Output is correct |
| 3 |
Correct |
13 ms |
15060 KB |
Output is correct |
| 4 |
Correct |
17 ms |
19776 KB |
Output is correct |
| 5 |
Correct |
18 ms |
20316 KB |
Output is correct |
| 6 |
Correct |
33 ms |
24932 KB |
Output is correct |
| 7 |
Correct |
9 ms |
14428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
18176 KB |
Output is correct |
| 2 |
Correct |
230 ms |
263032 KB |
Output is correct |
| 3 |
Correct |
143 ms |
36948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
58120 KB |
Output is correct |
| 2 |
Correct |
189 ms |
56680 KB |
Output is correct |
| 3 |
Correct |
224 ms |
92916 KB |
Output is correct |
| 4 |
Correct |
308 ms |
231172 KB |
Output is correct |
| 5 |
Correct |
252 ms |
192192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
42152 KB |
Output is correct |
| 2 |
Correct |
296 ms |
43708 KB |
Output is correct |
| 3 |
Correct |
778 ms |
327612 KB |
Output is correct |
| 4 |
Correct |
697 ms |
460996 KB |
Output is correct |
| 5 |
Correct |
397 ms |
188320 KB |
Output is correct |
| 6 |
Correct |
296 ms |
158276 KB |
Output is correct |
| 7 |
Correct |
236 ms |
121240 KB |
Output is correct |
| 8 |
Correct |
258 ms |
93520 KB |
Output is correct |
| 9 |
Correct |
363 ms |
45384 KB |
Output is correct |
