제출 #1021168

#제출 시각아이디문제언어결과실행 시간메모리
1021168Alihan_8바이러스 (JOI19_virus)C++17
6 / 100
589 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' //#define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } int dx[] = {0, -1, 0, 1}; int dy[] = {-1, 0, 1, 0}; struct Dsu{ vector <int> fa, pt, isDead; int n; Dsu(int n_){ n = n_; fa.resize(n); pt.resize(n); isDead.resize(n); for ( int i = 0; i < n; i++ ){ fa[i] = pt[i] = i; isDead[i] = false; } } int get(int u){ return fa[u] ^ u ? fa[u] = get(fa[u]) : u; } bool merge(int u, int v){ // u to v // cout << u << " " << v << ln; u = get(u), v = get(v); if ( u == v ){ return false; } fa[u] = v; return true; } void setDead(int u){ u = get(u); isDead[u] = true; } bool is(int u){ return isDead[get(u)]; } }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int m, r, c; cin >> m >> r >> c; string d; cin >> d; d += d; m *= 2; map <char,int> dir = {{'W', 0}, {'N', 1}, {'E', 2}, {'S', 3}}; vector <vector<int>> a(r, vector <int> (c)); vector <vector<vector<int>>> way(r, vector <vector<int>> (c)); vector <set<pair<int,int>>> st(16); for ( int i = 0; i < r; i++ ){ for ( int j = 0; j < c; j++ ){ cin >> a[i][j]; chmin(a[i][j], m); for ( int k = 0; k < 16; k++ ){ st[k].insert({a[i][j], i * c + j}); } } } { // initializing "way" vector <int> nxt(4, m); for ( int i = m - 1; i >= 0; i-- ){ nxt[dir[d[i]]] = i; vector <ar<int,2>> p_; for ( int j = 0; j < 4; j++ ){ p_.pb({nxt[j], j}); } sort(all(p_)); p_.pb({m + 1, 5}); int mask = 0; for ( int k = 0; k < 4; k++ ){ auto [x, j] = p_[k]; mask |= 1 << j; auto &s = st[mask]; int r = p_[k + 1][0] - i + 1; auto it = s.lower_bound({x - i + 1, -1}); vector <pair<int,int>> er; while ( it != s.end() && it -> first < r ){ int y = it -> second; way[y / c][y % c].pb(mask); er.pb(*it); it = next(it); } for ( auto &y: er ){ s.erase(y); } } } st.clear(); } if ( r > 50 || c > 50 ){ return cout << "-1\n", 0; } auto ok = [&](int x, int y){ return x >= 0 && y >= 0 && x < r && y < c && (a[x][y] != 0); }; Dsu ds(r * c); vector <vector<int>> us(r, vector <int> (c)); vector <ar<int,2>> tmp; auto clear = [&](){ for ( auto &[x, y]: tmp ){ us[x][y] = false; } tmp.clear(); }; auto bfs = [&](int su, int sv){ us[su][sv] = 1; int B = ds.get(su * c + sv); queue <ar<int,2>> q; q.push({su, sv}); ar <int,2> ret = {0, 0}; bool has = false; while ( !q.empty() ){ auto [u, v] = q.front(); q.pop(); tmp.pb({u, v}); for ( int i = 0; i < 4; i++ ){ int x = dx[i] + u, y = dy[i] + v; if ( !ok(x, y) || us[x][y] ){ continue; } bool flag = false; for ( auto &mask: way[x][y] ){ bool ok_ = true; for ( int j = 0; j < 4; j++ ){ if ( !(mask >> j & 1) ) continue; int tx = x + dx[j], ty = y + dy[j]; if ( !ok(tx, ty) || !us[tx][ty] ){ ok_ = false; } } flag |= ok_; } if ( flag > 0 ){ if ( ds.get(x * c + y) != B ){ // new component if ( ds.is(x * c + y) ){ has = true; ret = {-1, ds.get(x * c + y)}; } else if ( !has ){ ret = {-1, ds.get(x * c + y)}; } continue; } us[x][y] = true; q.push({x, y}); } } } if ( ret[0] != -1 ) ret = {tmp.size(), -1}; return ret; }; int mn = r * c + 1, freq = 0; for ( int _ = 1; _ <= 30; _++ ){ vector <ar<int,2>> pp(r * c); for ( int i = 0; i < r * c; i++ ){ if ( !a[i / c][i % c] ) continue; if ( ds.get(i) == i && !ds.is(i) ){ pp[i] = bfs(ds.pt[i] / c, ds.pt[i] % c); clear(); } } for ( int i = 0; i < r * c; i++ ){ if ( !a[i / c][i % c] ) continue; if ( ds.get(i) == i && !ds.is(i) ){ auto p = pp[i]; if ( p[0] == -1 ){ if ( ds.is(p[1]) ){ ds.setDead(i); } else{ ds.merge(i, p[1]); } } else{ if ( chmin(mn, p[0]) ){ freq = 1; } else if ( mn == p[0] ){ freq += 1; } ds.setDead(i); } clear(); } } } cout << mn << "\n" << freq * mn << ln; cout << '\n'; }

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

virus.cpp: In lambda function:
virus.cpp:242:44: warning: narrowing conversion of '(& tmp)->std::vector<std::array<int, 2> >::size()' from 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  242 |         if ( ret[0] != -1 ) ret = {tmp.size(), -1};
      |                                    ~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...