제출 #163935

#제출 시각아이디문제언어결과실행 시간메모리
163935ho94949바이러스 (JOI19_virus)C++17
14 / 100
607 ms62072 KiB
#include<bits/stdc++.h> using namespace std; int M, R, C; string D; int U[802][802]; int f[2][2][2][2]; bool dead[802][802]; int color[802][802]; int ufd[656565]; int minv = 1010101010; int ans = 0; int Find(int a) { if(a==ufd[a]) return a; return ufd[a] = Find(ufd[a]); } void Union(int a, int b) { ufd[Find(b)] = Find(a); } static int visv = 1; int doBFS(int a, int b) { int ans = 0; ++visv; queue<pair<int, int> > Q; Q.emplace(make_pair(a, b)); while(!Q.empty()) { auto[pa,pb] = Q.front(); Q.pop(); if(color[pa][pb] == visv) continue; color[pa][pb] = visv; ++ans; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; //printf("%d %d\n", pa, pb); for(int d=0; d<4; ++d) { int a = pa+dx[d], b = pb+dy[d]; if(0<=a&&a<R&&0<=b&&b<C) { if(U[a][b] == 0) continue; bool N = a>0 && color[a-1][b] == visv; bool S = a<R-1 && color[a+1][b] == visv; bool W = b>0 && color[a][b-1] == visv; bool E = b<C-1 && color[a][b+1] == visv; //printf("%d %d %d %d %d %d\n", a, b, N, S, W, E); if(f[N][S][W][E] >= U[a][b]) { Q.emplace(a, b); } } } } return ans; } void DF(vector<pair<int, int> > stables) { memset(color, 0, sizeof color); for(auto [a, b]: stables) { int res = doBFS(a, b); if(minv > res) { minv = res; ans = 0; } if(minv == res) ans += res; } cout << minv << endl << ans <<endl; } void solve() { vector<vector<pair<int, int> > > V; for(int i=0; i<R; ++i) for(int j=0; j<C; ++j) { vector<pair<int, int> > tv; if(U[i][j] != 0) { tv.emplace_back(i, j); V.push_back(tv); } } vector<pair<int, int> > stables; while(!V.empty()) { /* for(auto x: V) { for(auto y: x) cout << y.first<<","<<y.second << " "; cout <<endl; } cout<<"==\n"; */ int K = V.size(); vector<bool> deads(K, false); for(int i=0; i<K; ++i) ufd[i] = i; for(int i=0; i<K; ++i) { for(auto [a, b]: V[i]) color[a][b] = i; } for(int c=0; c<(int)V.size(); ++c) { bool isdead = true; int inflto = -1; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; for(auto [aa, bb]: V[c]) { for(int d=0; d<4; ++d) { int a = aa+dx[d], b=bb+dy[d]; if(a<0||b<0||a>=R||b>=C) continue; if(U[a][b] == 0) continue; bool N = a>0 && !dead[a-1][b] && color[a-1][b] == c; bool S = a<R-1 &&!dead[a+1][b] && color[a+1][b] == c; bool W = b>0 && !dead[a][b-1] && color[a][b-1] == c; bool E = b<C-1 && !dead[a][b+1] && color[a][b+1] == c; if(f[N][S][W][E] >= U[a][b]) { //U[a][b] is infected if(dead[a][b]) { isdead = false; break; } if(color[a][b] == c) continue; isdead=false; inflto = color[a][b]; break; } } if(!isdead) break; } if(isdead) { stables.push_back(V[c][0]); deads[c] = true; for(auto [a, b]: V[c]) dead[a][b] = true; } else { if(inflto == -1) { // dead by others deads[c] = true; for(auto [a, b]: V[c]) dead[a][b] = true; } else { //printf("%d %d\n", inflto, c); Union(inflto, c); } } } for(int c=0; c<K; ++c) { if(deads[c]) continue; int fc = Find(c); if(fc == c) continue; for(auto x: V[c]) V[fc].push_back(x); } vector<vector<pair<int, int> > > nv; for(int c=0; c<K; ++c) { if(deads[c]) continue; if(Find(c) == c) nv.push_back(V[c]); } V = nv; } DF(stables); } int main() { cin >> M >> R >> C; cin >> D; D += D; D += D; for(int i=0; i<R; ++i) for(int j=0; j<C; ++j) { cin >> U[i][j]; U[i][j] = min(U[i][j], M); } for(int n=0; n<=1; ++n) for(int s=0; s<=1; ++s) for(int w=0; w<=1; ++w) for(int e=0; e<=1; ++e) { int v = 0, cnt = 0; for(char q: D) { if(n == 1 && q == 'N' || s == 1 && q == 'S' || w == 1 && q == 'W' || e == 1 && q == 'E') ++cnt; else cnt = 0; v = max(v, cnt); } f[n][s][w][e] = v; } solve(); }

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

virus.cpp: In function 'int main()':
virus.cpp:194:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if(n == 1 && q == 'N' ||
                ~~~~~~~^~~~~~~~~~~
virus.cpp:196:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             w == 1 && q == 'W' ||
             ~~~~~~~^~~~~~~~~~~
virus.cpp:197:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             e == 1 && q == 'E') ++cnt;
             ~~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...