Submission #489532

#	Time	Username	Problem	Language	Result	Execution time	Memory
489532		Haruto810198	Virus Experiment (JOI19_virus)	C++17	0 / 100	70 ms	7480 KiB

virus

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// N, S, W, E (from)

int m;
vi str;
int r, c;
int def[810][810];
// immune -> def = INF
int len[16]; // len[mask] = longest substring
// continuous -> len = INF - 1

bool vis[810][810];
vector<pii> vised;

int res_min, res_cnt;

void bfs(int sx, int sy){
	
	vector<pii> qu;
	
	vis[sx][sy] = 1;
	vised.eb(sx, sy);
	FOR(i, 0, 3, 1){
		qu.eb(sx + dx[i], sy + dy[i]);
	}
	
	while(!qu.empty()){
		// check if v is not infected
		int vx = qu.back().F;
		int vy = qu.back().S;
		qu.pop_back();
		if(!(1 <= vx and vx <= r and 1 <= vy and vy <= c)) continue;
		if(vis[vx][vy]) continue;
		
		// check if v can be infected
		int mask = 0;
		FOR(i, 0, 3, 1){
			int ix = vx + dx[i], iy = vy + dy[i];
			if(vis[ix][iy]) mask += (1<<i);
		}
		
		// infect v
		if(def[vx][vy] <= len[mask]){
			vis[vx][vy] = 1;
			vised.eb(vx, vy);
			FOR(i, 0, 3, 1){
				qu.eb(vx + dx[i], vy + dy[i]);
			}
		}
	}
	
	int sz = szof(vised);
	if(sz < res_min){
		res_min = sz;
		res_cnt = 1;
	}
	else if(sz == res_min){
		res_cnt++;
	}
	
	//cerr<<"bfs("<<sx<<", "<<sy<<") = "<<viscnt<<endl;
	
	for(pii v : vised){
		vis[v.F][v.S] = 0;
	}
	vised.clear();

}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>m>>r>>c;
	FOR(i, 1, m, 1){
		char ch;
		cin>>ch;
		if(ch == 'N') str.pb(0);
		if(ch == 'S') str.pb(1);
		if(ch == 'W') str.pb(2);
		if(ch == 'E') str.pb(3);
	}
	
	FOR(i, 0, r+1, 1){
		FOR(j, 0, c+1, 1){
			def[i][j] = INF;
		}
	}

	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			cin>>def[i][j];
			if(def[i][j] == 0) def[i][j] = INF;
		}
	}
	
	// find len[]
	FOR(i, 0, m-1, 1){
		str.pb(str[i]);
	}
	
	FOR(mask, 0, 15, 1){
		int cur = 0;
		for(int i : str){
			if(mask & (1<<i)) cur++;
			else cur = 0;
			len[mask] = max(len[mask], cur);
		}
		if(len[mask] == szof(str)) len[mask] = INF - 1;
	}
	
	/*
	res_min = INF;
	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			if(def[i][j] < INF) bfs(i, j);
		}
	}
	*/
	
	cerr<<"W : "<<len[4]<<endl;
	cerr<<"E : "<<len[8]<<endl;
	
	res_min = INF;
	FOR(i, 1, r, 1){
		int il[810], ir[810];
		
		ir[0] = 0;
		FOR(j, 1, c, 1){
			if(def[i][j] == INF) continue;
			ir[j] = max(j, ir[j - 1]);
			//cerr<<"ir = "<<ir[j]<<endl;
			while(ir[j] < c and def[i][ir[j] + 1] <= len[4]){ // W
				ir[j]++;
			}
			//cerr<<"ir = "<<ir[j]<<endl;
		}
		/*
		cerr<<"ir : ";
		FOR(j, 1, c, 1){
			if(def[i][j] == INF) cerr<<"- ";
			else cerr<<ir[j]<<" ";
		}
		cerr<<endl;
		*/
		il[c + 1] = c + 1;
		for(int j = c; j >= 1; j--){
			il[j] = min(j, il[j + 1]);
			if(def[i][j] == INF){
				il[j] = c + 1;
				continue;
			}
			while(il[j] > 1 and def[i][il[j] - 1] <= len[8]){ // E
				il[j]--;
			}
		}
		/*	
		cerr<<"il : ";
		FOR(j, 1, c, 1){
			if(def[i][j] == INF) cerr<<"- ";
			else cerr<<il[j]<<" ";
		}
		cerr<<endl;
		*/
		//cerr<<"cnt : ";
		FOR(j, 1, c, 1){
			if(def[i][j] == INF){
				//cerr<<"- ";
				continue;
			}
			int cnt = ir[j] - il[j] + 1;
			if(cnt < res_min){
				res_min = cnt;
				res_cnt = 1;
			}
			else if(cnt == res_min){
				res_cnt++;
			}
			//cerr<<cnt<<" ";
		}
		//cerr<<endl;

	}
	
	cout<<res_min<<'\n'<<res_cnt<<'\n';
	
	return 0;

}

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