제출 #227333

#제출 시각아이디문제언어결과실행 시간메모리
227333wilwxk바이러스 (JOI19_virus)C++14
0 / 100
450 ms17580 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 805; char comb[112345]; int sick[20]; int resis[MAXN][MAXN]; int marc[MAXN][MAXN]; bool checked[MAXN][MAXN]; vector<pair<int, int> > perm; int x, n, m; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; int dc[] = {'E', 'S', 'W', 'N'}; void calc_comb() { for(int i = x+1; i <= x+x; i++) comb[i] = comb[i-x]; for(int mask = 0; mask < (1<<4); mask++) { int mx = 0, cnt = 0; for(int i = 1; i <= x+x; i++) { bool ok = 0; for(int k = 0; k < 4; k++) { if(((1<<k)&mask) && dc[k] == comb[i]) { ok = 1; cnt++; } } mx = max(mx, cnt); if(!ok) cnt = 0; } if(mx == x+x) mx = 1e6; sick[mask] = mx; // printf("mask[%d] -> %d\n", mask, mx); } } bool isvalid(int i, int j) { if(i < 1 || i > n) return 0; if(j < 1 || j > m) return 0; return 1; } int bfs(int ox, int oy) { int cnt = 0; vector<pair<int, int> > qu; qu.push_back({ox, oy}); int p = 0; while(p < qu.size()) { int ux, uy; tie(ux, uy) = qu[p++]; if(marc[ux][uy] == 1) continue; marc[ux][uy] = 1; cnt++; for(int k = 0; k < 4; k++) { int vx = ux + dx[k]; int vy = uy + dy[k]; if(!isvalid(vx, vy)) continue; if(marc[vx][vy] || resis[vx][vy] == 0) continue; int mask = 0; for(int k2 = 0; k2 < 4; k2++) { int vx2 = vx + dx[k2]; int vy2 = vy + dy[k2]; if(!isvalid(vx2, vy2)) continue; if(marc[vx2][vy2]) mask |= (1<<k2); } if(sick[mask] >= resis[vx][vy]) { // printf(" add %d %d - %d\n", vx, vy, mask); if(checked[vx][vy]) { for(auto cur : qu) marc[cur.first][cur.second] = 0; return -1; } marc[vx][vy] = 2; qu.push_back({vx, vy}); } } } for(auto cur : qu) marc[cur.first][cur.second] = 0; return cnt; } int main() { scanf("%d %d %d", &x, &n, &m); scanf(" %s", &comb[1]); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf("%d", &resis[i][j]); perm.push_back({i, j}); } } calc_comb(); int ans = n*m; int ans2 = 0; srand(time(0)); random_shuffle(perm.begin(), perm.end()); for(auto cur : perm) { int cx, cy; tie(cx, cy) = cur; checked[cx][cy] = 1; if(resis[cx][cy] == 0) continue; int val = bfs(cx, cy); // printf("%d %d >>> %d\n", cx, cy, val); if(val == -1) continue; if(val < ans) { ans = val; ans2 = 0; } if(val == ans) ans2 += ans; } printf("%d\n%d\n", ans, ans2); }

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

virus.cpp: In function 'int bfs(int, int)':
virus.cpp:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(p < qu.size()) {
        ~~^~~~~~~~~~~
virus.cpp: In function 'int main()':
virus.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &x, &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", &comb[1]);
  ~~~~~^~~~~~~~~~~~~~~~~
virus.cpp:94:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &resis[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...