Submission #135603

#	Time	Username	Problem	Language	Result	Execution time	Memory
135603		KLPP	Virus Experiment (JOI19_virus)	C++14	6 / 100	2056 ms	5948 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(){
  cin>>m>>r>>c;
  cin>>s;
  while(s.size()<100000){
    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,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];
  rep(i,0,r){
    rep(j,0,c){
      cin>>u[i][j];
      
    }
  }
  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;
}

Compilation message (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:77:9:
     rep(i,0,s.size()){
         ~~~~~~~~~~~~             
virus.cpp:77:5: note: in expansion of macro 'rep'
     rep(i,0,s.size()){
     ^~~
virus.cpp:90: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: 0 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80