제출 #290281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290281		TadijaSebez	바이러스 (JOI19_virus)	C++11	100 / 100	321 ms	20316 KiB

virus

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define x first
#define y second
#define mp make_pair
const int N=805;
const int M=200050;
const int inf=1e9+7;
char s[M];
pii p[N][N];
pii Find(int x,int y){return p[x][y]==mp(x,y)?mp(x,y):p[x][y]=Find(p[x][y].x,p[x][y].y);}
bool done[N][N];
void Union(int x1,int y1,int x2,int y2){
	tie(x1,y1)=Find(x1,y1);
	p[x1][y1]=Find(x2,y2);
}
int mxt[1<<4],U[N][N],tme,was[N][N],ans[N][N],mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void Expand(int x,int y){
	queue<pii> q;
	vector<pii> cells;
	tme++;
	q.push({x,y});was[x][y]=tme;
	while(q.size()){
		int x,y;tie(x,y)=q.front();
		cells.pb(q.front());
		q.pop();
		for(int i=0;i<4;i++){
			int nx=x+mv[i][0];
			int ny=y+mv[i][1];
			if(U[nx][ny]==0||was[nx][ny]==tme)continue;
			int mask=0;
			for(int j=0;j<4;j++)if(was[nx+mv[j][0]][ny+mv[j][1]]==tme)mask|=1<<j;
			if(U[nx][ny]<=mxt[mask]){
				if(Find(x,y)!=Find(nx,ny)){
					tie(nx,ny)=Find(nx,ny);
					if(done[nx][ny]){
						tie(x,y)=Find(x,y);
						done[x][y]=1;
					}else Union(x,y,nx,ny);
					return;
				}
				was[nx][ny]=tme;
				q.push({nx,ny});
			}
		}
	}
	tie(x,y)=Find(x,y);
	done[x][y]=1;
	for(pii p:cells)ans[p.x][p.y]=cells.size();
}
int main(){
	int n,m,k;
	scanf("%i %i %i",&k,&n,&m);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%i",&U[i][j]);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)p[i][j]=mp(i,j);
	for(int i=1;i<=k;i++)s[i+k]=s[i];
	k+=k;
	map<char,int> val;
	val['S']=0;
	val['E']=1;
	val['N']=2;
	val['W']=3;
	for(int i=1;i<=k;i++)s[i]=val[s[i]];
	for(int mask=0;mask<1<<4;mask++){
		for(int i=1,len=0;i<=k;i++){
			if(mask>>s[i]&1)len++;
			else len=0;
			mxt[mask]=max(mxt[mask],len);
		}
		if(mxt[mask]==k)mxt[mask]=inf;
	}
	while(1){
		bool ok=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(Find(i,j)==mp(i,j)&&!done[i][j]&&U[i][j]){
					Expand(i,j);
					ok=1;
				}
			}
		}
		if(!ok)break;
	}
	int mn=inf,cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ans[i][j]){
				if(mn>ans[i][j])mn=ans[i][j],cnt=0;
				if(mn==ans[i][j])cnt++;
			}
		}
	}
	printf("%i\n%i\n",mn,cnt);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

virus.cpp: In function 'int main()':
virus.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%i %i %i",&k,&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
virus.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%s",s+1);
      |  ~~~~~^~~~~~~~~~
virus.cpp:57:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%i",&U[i][j]);
      |                                            ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80