Submission #762792

#	Time	Username	Problem	Language	Result	Execution time	Memory
762792		MarwenElarbi	Virus Experiment (JOI19_virus)	C++17	0 / 100	4 ms	620 KiB

virus

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define fi first
#define se second
using namespace std;
const int MOD=1e9+7;
const int nax=1e5+5;
int arx[4]={1, -1, 0, 0};
int ary[4]={0, 0, -1, 1};
int m,r,c;
int mx[4];
int grid[50][50];
bool vis[50][50];
int dfs(int g,int h)
{
	int ans=0;
	queue<pair<int,int>> q;
	q.push({g,h});
	vis[g][h]=true;
	while(!q.empty()){
		int x=q.front().fi;
		int y=q.front().se;
		q.pop();
		vis[x][y]=true;
		for (int i = 0; i < 4; ++i)
		{
			int a=x+arx[i];
			int b=y+ary[i];
			if (a<0||a==r||b<0||b==c) continue;
			if (vis[a][b]) continue;
			if (grid[a][b]==0) continue;
			int k=0;
			for (int j = 0; j < 4; ++j)
			{
				int y=a+arx[j];
				int d=b+ary[j];
				if (y<0||y==r||d<0||d==c){
					continue;
				}
				if(grid[y][d]==0) continue;
				if (vis[y][d]){
					if (j<2){
						k+=mx[abs(1-j)];
					}else if(j==2) k+=mx[3];
					else k+=mx[2];
					
				}
			}
			if (k>=grid[a][b]){
				vis[a][b]=true;
				ans++;
				q.push({a,b});
			}
		}
	}
	return ans;
}
int main()
{
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif*/
	string t;
	cin>>m>>r>>c;
	cin>>t;
	int cur=0;
	memset(mx,0,sizeof mx);
	bool test=false;
	for (int i = 0; i < m; ++i)
	{
		int cur;
		if (!test) cur=0;
		if (t[i]=='W'){
			while(t[i]=='W'){
				i++;
				cur++;
			}
			mx[3]=max(mx[3],cur);
			i--;
			if (test) break;
		}else if(t[i]=='E'){
			while(t[i]=='E'){
				i++;
				cur++;
			}
			mx[2]=max(mx[2],cur);
			i--;
			if (test) break;
		}else if(t[i]=='S'){
			while(t[i]=='S'){
				i++;
				cur++;
			}
			mx[1]=max(mx[1],cur);
			i--;
			if (test) break;
		}else if(t[i]=='N'){
			while(t[i]=='N'){
				i++;
				cur++;
			}
			mx[0]=max(mx[0],cur);
			i--;
			if (test) break;	
		}
		if (i==m-1&&t[i]==t[0]){
			i=-1;
			test=true;
		}
	}
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cin>>grid[i][j];
		}
	}
	int ans=1e9;
	int time=0;
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (grid[i][j]==0) continue;
			memset(vis,0,sizeof vis);
			int cur=dfs(i,j);
			if (cur<ans){
				ans=cur;
				time=1;
			}else if(cur==ans) time++;
		}
	}
	cout << ans+1<<endl;
	cout << time<<endl;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:68:6: warning: unused variable 'cur' [-Wunused-variable]
   68 |  int cur=0;
      |      ^~~

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