結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー 小夫
提出日時 2025-03-30 14:28:10
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,746 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,181 ms
コンパイル使用メモリ 202,200 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-30 14:28:14
合計ジャッジ時間 4,572 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:79:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   79 |         for(int i=0;i<n;++i)scanf("%s",cl[i]);
      |                             ~~~~~^~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch&15);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return;
}
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char cl[100][100];
int cnt[2],match[2][10010],pre[10010],vis[10010];
vector<vector<int>>pk;
inline int syh()
{
	memset(match,-1,sizeof match);
	memset(vis,-1,sizeof vis);
	int l=pk.size();
	for(int i=0;i<l;++i)
	{
		stack<int>st;
		st.push(i);
		vis[i]=i,pre[i]=-1;
		bool fg=0;
		while(!st.empty())
		{
			int tp=st.top();
			st.pop();
			for(auto dg:pk[tp])
			{
				int k=match[1][dg];
				if(k==-1)
				{
					while(~tp)
					{
						match[1][dg]=tp;
						swap(dg,match[0][tp]);
						tp=pre[tp];
					}
					fg=1;
					break;
				}
				else if(vis[k]<i)
				{
					vis[k]=i;
					pre[k]=tp;
					st.push(k);
				}
			}
			if(fg)break;
		}
	}
	return l-count(match[0],match[0]+l,-1);
}
int main()
{
	int n=read(),m=read();
	pk.resize(n*m);
	for(int i=0;i<n;++i)scanf("%s",cl[i]);
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
		{
			int col=(i+j)&1,pos=i*m+j;
			if(cl[i][j]!='.')
			{
				++cnt[col];
				if(!col)
				{
					for(int dir=0;dir<4;++dir)
					{
						int x=i+dx[dir],y=j+dy[dir];
						if(x<0||x>=n||y<0||y>=m||cl[x][y]=='.')continue;
						pk[pos].emplace_back(x*m+y);
					}
				}
			}
		}
	int s1=syh();
	int s2=min(cnt[0],cnt[1])-s1;
	int s3=cnt[0]+cnt[1]-(s1+s2)*2;
	write(s1*100+s2*10+s3);
	return 0;
}
0