Submission #1004192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004192		vjudge1	Paint (COI20_paint)	C++17	0 / 100	3105 ms	132552 KiB

paint

#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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52