| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 907745 |
2024-01-16T04:04:05 Z |
ibm2006 |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
66892 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,m,ee,e;
vector<vector<ll>> a,h;
vector<vector<pair<ll,ll>>> par;
vector<vector<set<pair<ll,pair<ll,ll>>>>> v;
pair<ll,ll> p,q;
pair<ll,pair<ll,ll>> pq;
void adj(ll x,ll y)
{
ll i,j;
if(a[x+1][y]>=0)
{
v[x][y].insert({a[x+1][y],{x+1,y}});
}
if(a[x-1][y]>=0)
{
v[x][y].insert({a[x-1][y],{x-1,y}});
}
if(a[x][y+1]>=0)
{
v[x][y].insert({a[x][y+1],{x,y+1}});
}
if(a[x][y-1]>=0)
{
v[x][y].insert({a[x][y-1],{x,y-1}});
}
}
pair<ll,ll> f(ll x,ll y)
{
pair<ll,ll> p={x,y};
if(par[x][y]==p)
return p;
par[x][y]=f(par[x][y].first,par[x][y].second);
return par[x][y];
}
void g(ll x,ll y,ll z,ll w)
{
ll i;
pair<ll,ll> p,q;
p=f(x,y);
q=f(z,w);
if(p==q)
return;
x=p.first; y=p.second;
z=q.first; w=q.second;
if(h[x][y]>h[z][w])
{
h[x][y]+=h[z][w];
par[z][w]={x,y};
for(pair<ll,pair<ll,ll>> pa:v[z][w])
v[x][y].insert(pa);
v[z][w].clear();
return;
}
else
{
h[z][w]+=h[x][y];
par[x][y]={z,w};
for(pair<ll,pair<ll,ll>> pa:v[x][y])
v[z][w].insert(pa);
v[x][y].clear();
return;
}
}
int main()
{
scanf("%lld %lld",&n,&m);
a.resize(n+10);
v.resize(n+10);
par.resize(n+10);
h.resize(n+10);
for(i=0;i<=n+1;i++)
{
a[i].resize(m+10);
v[i].resize(m+10);
par[i].resize(m+10);
h[i].resize(m+10);
}
for(i=0;i<=n+1;i++)
{
for(j=0;j<=m+1;j++)
{
a[i][j]=-1;
par[i][j]={i,j};
h[i][j]=1;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%lld",&a[i][j]);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
adj(i,j);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(par[i][j]!=make_pair(i,j))
continue;
// printf("(%lld,%lld)\n",i,j);
while(1)
{
// printf("!");
z=i;
w=j;
p=f(z,w);
z=p.first;
w=p.second;
x=a[z][w];
// printf("?");
if(v[z][w].lower_bound({x,{0,0}})==v[z][w].end())
break;
pq=(*v[z][w].lower_bound({x,{0,0}}));
if(pq.first!=x)
break;
v[z][w].erase(pq);
// printf("@");
p=pq.second;
x=p.first;
y=p.second;
// printf("?");
// printf("(%lld,%lld)",x,y);
p=f(x,y);
// printf("!");
x=p.first;
y=p.second;
// printf("%lld,%lld,%lld,%lld\n",x,y,z,w);
g(x,y,z,w);
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
p=f(i,j);
x=p.first; y=p.second;
// printf("(%lld,%lld)",x,y);
// printf("%lld ",a[x][y]);
}
// printf("\n");
}
scanf("%lld",&e);
for(ee=0;ee<e;ee++)
{
scanf("%lld %lld %lld",&i,&j,&z);
p=f(i,j);
i=p.first;
j=p.second;
a[i][j]=z;
while(1)
{
// printf("!");
z=i;
w=j;
p=f(z,w);
z=p.first;
w=p.second;
x=a[z][w];
// printf("?");
if(v[z][w].lower_bound({x,{0,0}})==v[z][w].end())
break;
pq=(*v[z][w].lower_bound({x,{0,0}}));
if(pq.first!=x)
break;
v[z][w].erase(pq);
//printf("@");
p=pq.second;
p=f(p.first,p.second);
x=p.first;
y=p.second;
if(a[x][y]!=a[z][w])
continue;
// printf("?");
// printf("(%lld,%lld)",x,y);
p=f(x,y);
// printf("!");
x=p.first;
y=p.second;
// printf("%lld,%lld,%lld,%lld\n",x,y,z,w);
g(x,y,z,w);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
p=f(i,j);
x=p.first; y=p.second;
//printf("[%lld] ",a[x][y]);
}
// printf("\n");
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
p=f(i,j);
x=p.first; y=p.second;
printf("%lld ",a[x][y]);
}
printf("\n");
}
}
Compilation message
paint.cpp: In function 'void adj(ll, ll)':
paint.cpp:12:8: warning: unused variable 'i' [-Wunused-variable]
12 | ll i,j;
| ^
paint.cpp:12:10: warning: unused variable 'j' [-Wunused-variable]
12 | ll i,j;
| ^
paint.cpp: In function 'void g(ll, ll, ll, ll)':
paint.cpp:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
44 | if(p==q)
| ^~
paint.cpp:46:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
46 | x=p.first; y=p.second;
| ^
paint.cpp:40:8: warning: unused variable 'i' [-Wunused-variable]
40 | ll i;
| ^
paint.cpp: In function 'int main()':
paint.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%lld %lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%lld",&a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:153:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | scanf("%lld",&e);
| ~~~~~^~~~~~~~~~~
paint.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | scanf("%lld %lld %lld",&i,&j,&z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
3 ms |
964 KB |
Output is correct |
| 3 |
Incorrect |
151 ms |
3828 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3089 ms |
18768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3032 ms |
66892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3041 ms |
49272 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
