| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 554410 |
2022-04-28T10:50:22 Z |
leaked |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
80528 KB |
#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define vec vector
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=2e5+1;
const int K=200;
const int tx[4]={1,-1,0,0};
const int ty[4]={0,0,1,-1};
int who[K],p[N],cnt[N],id[N];
bitset<K> ust[N];
unordered_map<int,int> ids[N];
/// for comp lets mantain colours
vec<vec<int>> go[N];
void addj(int v,int x,int y){
if(ids[v].find(x)==ids[v].end()){
go[v].pb(vec<int>());
ids[v][x]=sz(ids[v]);
}
// assert(sz(go[v])==sz(ids[v]));
go[v][ids[v][x]].pb(y);
}
int get(int v){
// cout<<"VT "<<v<<endl;
return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg(int a,int b,bool need=0){
// cout<<"MEG "<<a<<' '<<b<<endl;
a=get(a),b=get(b);
// cout<<"MEG "<<a<<' '<<b<<endl;
if(a==b) return 0;
if(cnt[a]>cnt[b]) swap(a,b);
for(auto &z : ids[a]){
for(auto &u : go[a][z.s])
addj(b,z.f,u);
}
ids[a].clear();go[a].clear();
if(id[a]!=-1) id[b]=id[a];
// ust[b]|=ust[a];/// n*k/64;
p[a]=b;cnt[b]+=cnt[a];
// cout<<"IMG "<<a<<' '<<b<<endl;
if(need){
ust[b]|=ust[a];/// n*k/64;
if(id[b]!=-1){
for(int j=0;j<K;j++){
// cout<<"WOW "<<who[j]<<endl;
if(ust[b][j] && who[j]!=-1){
// cout<<"NO "<<endl;
ust[get(who[j])][id[b]]=1;
}
}
}
}
// cout<<"EXIT "<<endl;
return 1;
}
int n,m;
int idl(int i,int j){
return i*m+j;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
iota(p,p+N,0);fill(cnt,cnt+N,1);
cin>>n>>m;
vec<vec<int>>a(n,vec<int>(m));
vec<int>b(n*m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
b[i*m+j]=a[i][j];
}
}
int q;
cin>>q;
vec<int> ii(q),jj(q),c(q);
for(int i=0;i<q;i++){
cin>>ii[i]>>jj[i]>>c[i];--ii[i];--jj[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i && a[i-1][j]==a[i][j]) mg(idl(i,j),idl(i-1,j));
if(j && a[i][j-1]==a[i][j]) mg(idl(i,j),idl(i,j-1));
}
}
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++)
// cout<<ds.get(id(i,j))<<' ';
// cout<<'\n';
// }
// return 0;
vec<int>used(n*m,-1);
int tt=1;
fill(who,who+K,-1);
for(int t=0;t<q;t+=K){
int l=t,r=min(q,t+K);
for(int i=0;i<n*m;i++) id[i]=-1,ids[i].clear(),go[i].clear();
++tt;
for(int i=l;i<r;i++){
int v=get(idl(ii[i],jj[i]));
who[i-l]=-1;
if(used[v]!=t){
id[v]=i-l;
used[v]=t;
who[i-l]=v;
}
}
/// very bad
for(int i=0;i<n*m;i++){
if(get(i)==i)
ust[i].reset();
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int v=get(idl(i,j));
for(int x=0;x<4;x++){
int ni=tx[x]+i,nj=ty[x]+j;
if(ni>=0&&ni<n&&nj>=0&&nj<m){
int u=get(idl(ni,nj));
if(used[v]==t)
ust[u][id[v]]=1;
// if(v==6)
// cout<<"ADD "<<i<<' '<<j<<' '<<' '<<b[u]<<' '<<u<<endl;
addj(v,b[u],u);
}
}
}
}
for(int i=l;i<r;i++){
int v=get(idl(ii[i],jj[i]));
b[v]=c[i];
// cout<<"ID "<<v<<' '<<b[v]<<' '<<c[i]<<endl;
if(ids[v].find(b[v])!=ids[v].end()){
int j=ids[v][b[v]];
// cout<<sz(go[v][j])<<endl;
vec<int> me=go[v][j];
for(auto &z : me){
// cout<<"ZET "<<z<<' '<<sz(go[v][j])<<endl;
if(b[get(z)]==b[v])
mg(v,z,1);
}
// cout<<"EXIT"<<endl;
go[v][j].clear();
}
for(int j=0;j<K;j++){
if(who[j]!=-1 && b[get(who[j])]==b[v] && ust[v][j])
mg(who[j],v,1);
}
}
// cout<<"DEBUG "<<endl;
//// for(int i=0;i<n;i++){
//// for(int j=0;j<m;j++)
//// cout<<b[get(idl(i,j))]<<' ';
// cout<<'\n';
// }
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
cout<<b[get(idl(i,j))]<<' ';
cout<<'\n';
}
return 0;
}
/*
6 6
1 2 1 2 2 2
2 1 2 1 3 1
2 3 3 2 3 2
2 2 1 2 2 2
2 2 2 2 2 2
2 2 2 2 2 1
6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 2 2 2 2 1
6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 2 2 2 2 1
6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 2 2 2 2 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
17876 KB |
Output is correct |
| 2 |
Correct |
11 ms |
17956 KB |
Output is correct |
| 3 |
Correct |
119 ms |
22704 KB |
Output is correct |
| 4 |
Correct |
149 ms |
21392 KB |
Output is correct |
| 5 |
Correct |
118 ms |
20712 KB |
Output is correct |
| 6 |
Correct |
91 ms |
20484 KB |
Output is correct |
| 7 |
Correct |
10 ms |
17492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3064 ms |
34956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3034 ms |
67792 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3049 ms |
80528 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
