제출 #135755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135755		KLPP	바이러스 (JOI19_virus)	C++14	20 / 100	358 ms	5164 KiB

virus

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int m,r,c;
string s;
int best[(1<<4)];
bool visited[1000][1000];
int u[1000][1000];
int dir(char c){
  if(c=='N')return 0;
  if(c=='S')return 1;
  if(c=='E')return 2;
  if(c=='W')return 3;
}
int resp(int x, int y){
  int msk=0;
  if(x>0 && visited[x-1][y]){
    msk+=1;
  }
  if(x<r-1 && visited[x+1][y]){
    msk+=2;
  }
  if(y<c-1 && visited[x][y+1]){
    msk+=4;
  }
  if(y>0 && visited[x][y-1]){
    msk+=8;
  }
  return msk;
}
void DFS(int x,int y){
  //cout<<x<<" "<<y<<endl;
  visited[x][y]=true;
  if(x>0 && !visited[x-1][y]){
    int msk=resp(x-1,y);
    if(best[msk]>=u[x-1][y] && u[x-1][y]!=0){
      DFS(x-1,y);
    }
  }
  if(x<r-1 && !visited[x+1][y]){
    int msk=resp(x+1,y);
    if(best[msk]>=u[x+1][y] && u[x+1][y]!=0){
      DFS(x+1,y);
    }
  }
  if(y>0 && !visited[x][y-1]){
    int msk=resp(x,y-1);
    if(best[msk]>=u[x][y-1] && u[x][y-1]!=0){
      DFS(x,y-1);
    }
  }
  if(y<c-1 && !visited[x][y+1]){
    int msk=resp(x,y+1);
    if(best[msk]>=u[x][y+1] && u[x][y+1]!=0){
      DFS(x,y+1);
    }
  }
}

int main(){
  srand(time(NULL));
  cin>>m>>r>>c;
  cin>>s;
  /*rep(i,0,s.size()){
    if(rand()%2==0)s[i]='E';
    else s[i]='W';
  }*/
  while(s.size()<200000){
    s=s+s;
  }
  //cout<<s<<endl;
  
  rep(i,0,4){
    best[i]=0;
  }
  rep(msk,0,16){
    int sz=0;
    best[msk]=0;
    rep(i,0,s.size()){
      if(((1<<(dir(s[i])))&msk)>0){
	sz++;
      }else sz=0;
      best[msk]=max(best[msk],sz);
    }
  }
   rep(i,0,r){
    rep(j,0,c){
      cin>>u[i][j];
      
    }
  }
  if(r>50 || c>50){
    int answers[1000];
    int edge[1000];
    lld ans1,ans2;
    vector<int> sizes;
      vector<int> edges;
    ans1=1000000000;
    ans2=0;
    //rep(i,0,16)cout<<best[i]<<endl;
    rep(i,0,r){
      //cout<<i<<endl;
      rep(j,1,c){
	edge[j-1]=0;
	if(u[i][j]!=0 && u[i][j-1]!=0){
	  if(best[4]>=u[i][j-1]){
	    edge[j-1]++;
	  }
	  if(best[8]>=u[i][j]){
	    edge[j-1]+=2;
	  }
	}
	//cout<<edge[j-1]<<" ";
      }//cout<<endl;
      sizes.clear();
      edges.clear();
      sizes.push_back(1);
      rep(j,0,c-1){
	if(edge[j]==3){
	  sizes[sizes.size()-1]++;
	}else{
	  sizes.push_back(1);
	  edges.push_back(edge[j]);
	}
      }
      rep(j,0,sizes.size()){
	answers[j]=sizes[j];
	if(j>0 && edges[j-1]==1){
	  answers[j]+=answers[j-1];
	}
	if(j<sizes.size()-1 && edges[j]==2){
	  int ptr=j;
	  while(ptr<edges.size() && edges[ptr]==2){
	    ptr++;
	  }
	  answers[ptr]=sizes[ptr];
	  for(int k=ptr-1;k>j;k--){
	    answers[k]=answers[k+1]+sizes[k];
	  }
	  answers[j]+=answers[j+1];
	  j=ptr;
	}
      }
      /*rep(j,0,sizes.size()){
	cout<<answers[j]<<" ";
      }cout<<endl;
      rep(j,0,edges.size()){
	cout<<edges[j]<<" ";
      }cout<<endl;*/
      int ptr=0;
      rep(j,0,sizes.size()){
	//cout<<ptr<<endl;
	if(u[i][ptr]!=0){
	  if(ans1>answers[j]){
	    ans1=answers[j];
	    ans2=0;
	  }
	  if(ans1==answers[j])ans2+=sizes[j];
	}
	ptr+=sizes[j];
      }
    }
    cout<<ans1<<endl<<ans2<<endl;
    return 0;
  }
  /*rep(i,0,16)cout<<best[i]<<" ";
    cout<<endl;*/
  /*rep(i,0,10)cout<<chain[i]<<","<<s[i]<<" ";
  cout<<endl;
  rep(i,0,4)cout<<best[i]<<" ";
  cout<<endl;*/
  int U[r*c];
  
  lld ans1,ans2;
  ans1=1000000000;
  ans2=0;
  rep(i,0,r){
    rep(j,0,c){
      rep(k,0,r){
	rep(l,0,c){
	  visited[k][l]=false;
	}
      }
    if(u[i][j]>0){
      DFS(i,j);
      lld can=0;
      rep(k,0,r){
	rep(l,0,c){
	  can+=visited[k][l];
	}
      }
      if(can<ans1){
	ans1=can;
	ans2=0;
      }
      if(can==ans1)ans2++;
      //cout<<can<<" "<<i<<" "<<j<<endl;
    }
    }
  }//cout<<endl;
  cout<<ans1<<endl<<ans2<<endl;
  //DFS(2,0);
  return 0;
}

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

virus.cpp: In function 'int main()':
virus.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
virus.cpp:82:9:
     rep(i,0,s.size()){
         ~~~~~~~~~~~~             
virus.cpp:82:5: note: in expansion of macro 'rep'
     rep(i,0,s.size()){
     ^~~
virus.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
virus.cpp:129:11:
       rep(j,0,sizes.size()){
           ~~~~~~~~~~~~~~~~       
virus.cpp:129:7: note: in expansion of macro 'rep'
       rep(j,0,sizes.size()){
       ^~~
virus.cpp:134:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(j<sizes.size()-1 && edges[j]==2){
     ~^~~~~~~~~~~~~~~
virus.cpp:136:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ptr<edges.size() && edges[ptr]==2){
          ~~~^~~~~~~~~~~~~
virus.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
virus.cpp:154:11:
       rep(j,0,sizes.size()){
           ~~~~~~~~~~~~~~~~       
virus.cpp:154:7: note: in expansion of macro 'rep'
       rep(j,0,sizes.size()){
       ^~~
virus.cpp:175:7: warning: unused variable 'U' [-Wunused-variable]
   int U[r*c];
       ^
virus.cpp: In function 'int dir(char)':
virus.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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