제출 #489533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489533		fhvirus	바이러스 (JOI19_virus)	C++17	14 / 100	462 ms	44372 KiB

virus

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int, int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I> bool chmin(I&a, I b){ return a > b ? (a=b, true) : false; }
template<class I> bool chmax(I&a, I b){ return a < b ? (a=b, true) : false; }
#ifdef OWO
#define debug(args...) LKJ("\033[1;32m[ " + string(#args) + " ]\033[0m", args)
template<class I> void LKJ(I&&x){ cerr << x << endl; }
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr << x << ", "; LKJ(t...); }
template<class I> void OI(I a, I b){ while(a < b) cerr << *a << " \n"[next(a) == b], ++a; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

const int kM = 100001;
const int kN = 808;
const int dx[4] = { 1, -1, 0, 0 };
const int dy[4] = { 0, 0, 1, -1 };
int code(char c){
	if(c == 'S') return 0;
	if(c == 'N') return 1;
	if(c == 'E') return 2;
	if(c == 'W') return 3;
}

int M, R, C, D[kM];
int U[kN][kN];

void input(){
	cin >> M >> R >> C;
	string in; cin >> in;
	for(int i = 0; i < M; ++i)
		D[i+1] = code(in[i]);
	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= C; ++j)
			cin >> U[i][j];
}

bitset<kM> msk[16];
bitset<16> all;
int mxl[16];
void init(){
	for(int i = 0; i < 4; ++i)
		for(int j = 1; j <= M; ++j)
			msk[1<<i][j] = (D[j] == i);

	for(int i = 0; i < 16; ++i)
		for(int l = 0; l < 4; ++l)
			if(i >> l & 1) msk[i] |= msk[1<<l];

	all.set();
	for(int i = 0; i < 16; ++i)
		for(int j = 1; j <= M; ++j)
			all[i] = all[i] & msk[i][j];

	for(int i = 0; i < 16; ++i){
		vector<int> pre(M+1, 0);
		for(int j = 1; j <= M; ++j)
			pre[j] = (msk[i][j]);
		for(int j = 1; j <= M; ++j)
			if(pre[j] != 0) pre[j] += pre[j-1];

		mxl[i] = *max_element(AI(pre));
		if(!all[i]) for(int j = 1; j <= M; ++j)
			if(pre[j] == 0){
				chmax(mxl[i], pre[j-1] + pre[M]);
				break;
			}
	}
}

int can[kN][kN][16];
bool vis[kN][kN];
int bfs(int si, int sj, int upb){
	for(int i = 1; i <= R; ++i)
	 	for(int j = 1; j <= C; ++j)
	 		vis[i][j] = 0;

	int cnt = 1;
	queue<pii> q;
	vis[si][sj] = true;
	q.emplace(si, sj);

	auto upd = [&](int i, int j){
		int m = 0;
		for(int l = 0; l < 4; ++l)
		for(int l = 2; l < 4; ++l)
			if(vis[i + dx[l]][j + dy[l]])
				m |= (1<<l);
		if(can[i][j][m]){
			vis[i][j] = 1;
			q.emplace(i, j);
			++cnt;
		}
	};

	while(!q.empty() and cnt <= upb){
		auto [i, j] = q.front(); q.pop();
		for(int d = 0; d < 4; ++d){
			int x = i + dx[d];
			int y = j + dy[d];
			if(x < 1 or x > R or y < 1 or y > C) continue;
			if(vis[x][y]) continue;
			upd(x, y);
		}
	}

	if(cnt > upb) return 1e9;
	return cnt;
}
int eek(int si, int sj){
	int l = sj, r = sj;
	while(can[si][l-1][4]) --l;
	while(can[si][r+1][8]) ++r;
	debug(si, sj, l, r);
	return r - l + 1;
}
void solve(){
	init();

	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= C; ++j){
			if(U[i][j] == 0) continue;
			for(int b = 0; b < 16; ++b)
				if(all[b] or mxl[b] >= U[i][j])
					can[i][j][b] = true;
		}

	int ans = 1e9;
	int anss = 0;
	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= C; ++j){
			if(U[i][j] == 0) continue;
			int d = (all[12] ? eek(i, j) : bfs(i, j, ans));
			if(chmin(ans, d)) anss = 1;
			else if(ans == d) ++anss;
		}

	cout << ans << '\n' << anss << '\n';
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	input();
	solve();
	return 0;
}

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

virus.cpp: In function 'int eek(int, int)':
virus.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
virus.cpp:120:2: note: in expansion of macro 'debug'
  120 |  debug(si, sj, l, r);
      |  ^~~~~
virus.cpp: In function 'int code(char)':
virus.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^

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