Submission #503224

#TimeUsernameProblemLanguageResultExecution timeMemory
503224amunduzbaevVirus Experiment (JOI19_virus)C++14
100 / 100
875 ms18408 KiB
#include "bits/stdc++.h" using namespace std; #define ar array //~ #define int long long signed main(){ mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios::sync_with_stdio(0); cin.tie(0); int k, n, m; cin>>k>>n>>m; string s; cin>>s; s += s; vector<int> mx(1 << 4, 0), cur(1 << 4, 0); for(int i=0;i<2*k;i++){ int c = 0; if(s[i] == 'N') c = 0; if(s[i] == 'E') c = 1; if(s[i] == 'S') c = 2; if(s[i] == 'W') c = 3; for(int mask=0;mask<16;mask++){ if(mask >> c & 1) cur[mask]++; else cur[mask] = 0; mx[mask] = max(mx[mask], cur[mask]); } } for(int i=0;i<16;i++){ if(mx[i] >= k) mx[i] = 1e9 + 7; } vector<vector<int>> a(n, vector<int>(m)); vector<int> ord; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; if(a[i][j]) ord.push_back(i * m + j); } } shuffle(ord.begin(), ord.end(), rng); int res = 1e9, cnt = 0; vector<vector<int>> t(n, vector<int>(m)), used(n, vector<int>(m)); int tt = 0; for(auto x : ord) t[x/m][x%m] = ++tt; int ch[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; auto check = [&](int i, int j){ if(!(0 <= i && i < n && 0 <= j && j < m) || a[i][j] == 0) return false; int tot = 0; for(int t=0;t<4;t++){ int x = i + ch[t][0], y = j + ch[t][1]; if(0 <= x && x < n && 0 <= y && y < m && used[x][y]) tot |= (1 << t); } return (mx[tot] >= a[i][j]); }; for(auto x : ord){ int i = x/m, j = x%m; vector<int> tot; tot.push_back(x); queue<int> qq; qq.push(x); used[i][j] = 1; bool flag = 1; while(!qq.empty() && flag){ int x = qq.front() / m, y = qq.front() % m; qq.pop(); for(int k=0;k<4;k++){ int r = x + ch[k][0], c = y + ch[k][1]; if(check(r, c) && !used[r][c]) { used[r][c] = 1, qq.push(r * m + c); tot.push_back(r * m + c); if(t[r][c] < t[i][j]) { flag = 0; break; } } } } for(auto x : tot) used[x/m][x%m] = 0; if(!flag) continue; int sz = (int)tot.size(); if(sz < res) res = sz, cnt = 0; cnt += (sz == res); } cout<<res<<"\n"<<cnt * res<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...