# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1004192 |
2024-06-21T06:19:44 Z |
vjudge1 |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
132552 KB |
#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 1;
bool vis[M];
int col[M],sz[M],r,s,a[M],rcol[M];
vector<int> ver[M];
map<int,set<int>> nei[M];
bool valid(int u)
{
return u>=0 && u<r*s;
}
void dfs(int u)
{
vis[u]=true;
sz[col[u]]++;
ver[col[u]].push_back(u);
for (int px=-1;px<=1;px++)
for (int py=-1;py<=1;py++)
{
if ((px==0)==(py==0))
continue;
int v=u+px+py*s;
if (valid(v) && (v/s==u/s || v%s==u%s) && !vis[v] && a[v]==a[u])
{
col[v]=col[u];
dfs(v);
}
}
}
int main()
{
cin>>r>>s;
for (int i=0;i<r*s;i++)
cin>>a[i];
int x=0;
for (int i=0;i<r*s;i++)
if (!vis[i])
{
col[i]=++x;
dfs(i);
rcol[x]=a[i];
}
for (int i=0;i<r*s;i++)
vis[i]=0;
for (int i=0;i<r*s;i++)
{
if (vis[i])
continue;
for (int u:ver[col[i]])
{
vis[u]=true;
for (int px=-1;px<=1;px++)
for (int py=-1;py<=1;py++)
{
if ((px==0)==(py==0))
continue;
int v=u+px+py*s;
if (valid(v) && (v/s==u/s || v%s==u%s) && !vis[v] && col[v]!=col[u])
{
nei[col[u]][a[v]].insert(col[v]);
nei[col[v]][a[u]].insert(col[u]);
}
}
}
}
int q;
cin>>q;
while (q--)
{
int n,m,b;
cin>>n>>m>>b;
int x=n*s+m-s-1;
int a=rcol[col[x]];
if (a==b)
continue;
if (nei[col[x]].find(b)!=nei[col[x]].end())
{
set<pair<int,int>,greater<pair<int,int>>> se;
se.insert({sz[col[x]],col[x]});
for (auto i:nei[col[x]][b])
se.insert({sz[i],i});
auto p=*se.begin();
se.erase(p);
for (auto q:nei[p.second])
for (auto w:q.second)
{
nei[w][a].erase(p.second);
nei[w][b].insert(p.second);
}
for (auto i:se)
{
int u=i.second;
for (auto q:nei[u])
for (auto w:q.second)
{
nei[p.second][q.first].insert(w);
nei[w][b].erase(u);
nei[w][b].insert(p.second);
}
for (int v:ver[u])
{
col[v]=p.second;
ver[p.second].push_back(v);
sz[p.second]++;
}
ver[u].clear();
sz[u]=0;
}
rcol[p.second]=b;
}
else
{
for (auto p:nei[col[x]])
for (auto i:p.second)
{
nei[i][a].erase(col[x]);
nei[i][b].insert(col[x]);
}
rcol[col[x]]=b;
}
}
for (int i=0;i<r*s;i++)
vis[i]=0;
int ans[r][s];
for (int i=0;i<r*s;i++)
{
if (vis[i])
continue;
for (auto j:ver[col[i]])
{
vis[j]=1;
ans[j/s][j%s]=rcol[col[i]];
}
}
for (int i=0;i<r;i++)
{
for (int j=0;j<s;j++)
cout<<ans[i][j]<<' ';
cout<<endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14936 KB |
Output is correct |
2 |
Correct |
11 ms |
14940 KB |
Output is correct |
3 |
Correct |
22 ms |
22080 KB |
Output is correct |
4 |
Incorrect |
139 ms |
23808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
235 ms |
46928 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3076 ms |
92084 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3105 ms |
132552 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |