제출 #1217303

#제출 시각아이디문제언어결과실행 시간메모리
1217303JooDdaeVirus Experiment (JOI19_virus)C++20
100 / 100
416 ms149896 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define id(x, y) ((x-1)*m+y-1) #define coord(id) make_pair(id/m+1, id%m+1) const string S = "NSWE"; const int dx[4] = {-1, 1, 0 ,0}, dy[4] = {0, 0, -1, 1}; int n, m, k, c[100100], a[808][808], p[700700], mx[16], chk[700700], chk2[808][808][4], out[700700]; vector<int> v[700700], nxt[700700], used[700700]; string s; int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); } int findEdge(int x, int y, int d, int P) { if(!a[x][y] || chk2[x][y][d]) return -1; int B = 0; for(int i=0;i<4;i++) { int xx = x+dx[i], yy = y+dy[i]; if(1 <= xx && xx <= n && 1 <= yy && yy <= m && find(id(xx, yy)) == find(P)) B |= 1 << i; } if(mx[B] >= a[x][y]) { chk2[x][y][d] = 1; return id(x, y); } return -1; } void merge(int x, int y) { if((x = find(x)) == (y = find(y))) return; if(v[x].size() < v[y].size()) swap(v[x], v[y]); if(nxt[x].size() < nxt[y].size()) swap(nxt[x], nxt[y]); p[y] = x; for(auto i : nxt[y]) nxt[x].push_back(i); for(auto i : v[y]) { v[x].push_back(i); auto [X, Y] = coord(i); for(int i=0;i<4;i++) { auto B = findEdge(X+dx[i], Y+dy[i], i^1, x); if(B != -1) nxt[x].push_back(B); } } nxt[y].clear(), v[y].clear(); } vector<int> st; void dfs(int u) { u = find(u); if(chk[u] == 2) return; if(chk[u] == 1) { for(int i=int(st.size())-1;st[i]!=u;i--) merge(u, find(st[i])); return; } chk[u] = 1; st.push_back(u); while(!nxt[u].empty()) { int x = find(nxt[u].back()); nxt[u].pop_back(); if(x == find(u)) continue; used[u].push_back(x), dfs(x); } chk[u] = 2; st.pop_back(); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> k >> n >> m >> s; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j]; for(int i=0;i<n*m;i++) p[i] = i, v[i].push_back(i); for(int i=0;i<k;i++) c[i] = 1 << (find(S.begin(), S.end(), s[i]) - S.begin()); for(int b=1;b<16;b++) { for(int i=0;i<k;i++) if(c[i] & b) { int j = (i+1)%k, cnt = 1; while(j != i && (c[j] & b)) j = (j+1)%k, cnt++; mx[b] = max(mx[b], cnt); if(j <= i) break; i = j; } if(mx[b] == k) mx[b] = 1e9; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) for(int d=0;d<4;d++) { auto B = findEdge(i+dx[d], j+dy[d], d^1, id(i, j)); if(B != -1) nxt[id(i, j)].push_back(B); } for(int i=0;i<n*m;i++) if(!chk[i]) dfs(i); int cnt = 1e9, cnt2 = 0; for(int i=0;i<n*m;i++) if(i == find(i) && a[i/m+1][i%m+1]) { bool flag = 0; for(auto u : v[i]) for(auto x : used[u]) if(find(u) != find(x)) flag = 1; if(flag) continue; if(v[i].size() < cnt) cnt = v[i].size(), cnt2 = 1; else if(v[i].size() == cnt) cnt2++; } cout << cnt << "\n" << cnt * cnt2 << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...