QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#815880 | #1127. Virus Experiment | _8_8_ | 0 | 3ms | 16232kb | C++23 | 5.6kb | 2024-12-15 18:20:50 | 2024-12-15 18:20:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e6 + 12, MOD = 998244353, maxn = 805;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, r, c, u[maxn][maxn], mx = 0, e[N], p[N];
string s;
vector<int> w[N], st[N];
int o;
int conv(int x, int y) {
return (x - 1) * c + y;
}
bool bl[N];
int lst_a = -1;
pair<int, int> ob[N];
vector<int> g[N];
set<int> rts;
void prec() {
cin >> s;
for(int i = 1; i <= r; i++) {
for(int j = 1; j <= c; j++) {
cin >> u[i][j];
if(!u[i][j]) {
u[i][j] = (int)1e9;
bl[conv(i, j)] = 1;
}
ob[conv(i, j)] = {i, j};
}
}
for(int i = 0; i < n; i++) {
if(s[i] == 'N') {
e[i] = 0;
} else if(s[i] == 'S') {
e[i] = 2;
} else if(s[i] == 'E') {
e[i] = 3;
} else {
e[i] = 1;
}
}
for(int i = 1; i < (1 << 4); i++) {
vector<int> f;
for(int j = 0; j < n; j++) {
if(!((i >> e[j]) & 1)) f.push_back(j);
}
int mx = 0;
if(f.empty()) {
mx = (int)1e6;
} else {
mx = f[0] + (n - 1 - f.back());
for(int l = 1; l < (int)f.size(); l++) {
mx = max(mx, f[l] - f[l - 1] - 1);
}
}
for(int x = 1; x <= r; x++) {
for(int y = 1; y <= c; y++) {
if(u[x][y] > mx) continue;
bool ok = 1;
if(x == r || x == 1 || y == 1 || y == c) {
for(int j = 0; j < 4; j++) {
if((i >> j) & 1) {
int kx = x - dx[j], ky = y - dy[j];
if(kx >= 1 && kx <= r && ky >= 1 && ky <= c) {
} else {
ok = 0;
break;
}
}
}
}
if(!ok) continue;
w[conv(x, y)].push_back(i);
}
}
}
n = r * c;
for(int i = 1; i <= n; i++) {
p[i] = i;
st[i].push_back(i);
rts.insert(i);
for(int j : w[i]) {
if(__builtin_popcount(j) == 1) {
for(int k = 0; k < 4; k++) {
if((j >> k) & 1) {
int kx = ob[i].first - dx[k], ky = ob[i].second - dy[k];
g[conv(kx, ky)].push_back(i);
// cout << conv(kx, ky) << ' ' << i << ' ' << j << '\n';
break;
}
}
}
}
}
}
vector<int> ans;
void out() {
sort(ans.begin(), ans.end());
int res = 0;
for(int i = 0; i < (int)ans.size() && ans[i] == ans[0]; i++) {
res += ans[i];
}
cout << ans[0] << '\n' << res << '\n';
}
int get(int v) {
if(p[v] == v) return v;
return p[v] = get(p[v]);
}
bool check(int i, int f) {
for(int j : w[i]) {
bool ok = 1;
for(int k = 0; k < 4; k++) {
if((j >> k) & 1) {
int x = ob[i].first - dx[k], y = ob[i].second - dy[k];
assert(x >= 1 && x <= r && y >= 1 && y <= c);
if(get(conv(x, y)) != f) {
ok = 0;
break;
}
}
}
if(ok) return 1;
}
return 0;
}
void merge(int v, int u) {
v = get(v);
u = get(u);
p[v] = u;
for(int i : g[v]) {
i = get(i);
if(i == u) continue;
g[u].push_back(i);
}
for(int i : st[v]) {
st[u].push_back(i);
for(int j = 0; j < 4; j++) {
int x = dx[j] + ob[i].first, y = dy[j] + ob[i].second;
if(x >= 1 && x <= r && y >= 1 && y <= c) {
if(get(conv(x, y)) == u) continue;
if(check(conv(x, y), u)) {
// if(u == 1)cout << u << ' ' << conv(x, y) << "x\n";
g[u].push_back(conv(x, y));
}
}
}
}
}
int vis[N];
vector<int> pa;
void dfs(int v) {
vis[v] = 1;
pa.push_back(v);
bool is = 0;
// cout << v << '\n';
for(int it = 0; it < (int)g[v].size(); it++) {
int to = g[v][it];
to = get(to);
if(to == v) continue;
if(vis[to] == 1) {
is = 1;
while(!pa.empty() && pa.back() != to) {
int x = pa[(int)pa.size() - 1], y = pa[(int)pa.size() - 2];
merge(x, y);
pa.pop_back();
}
pa.pop_back();
pa.push_back(get(to));
v = get(v);
} else if(!vis[to]) {
dfs(to);
}
}
vis[v] = 2;
pa.pop_back();
}
void test() {
cin >> n >> r >> c;
prec();
for(int i = 1; i <= n; i++) {
if(bl[i] || get(i) != i) continue;
dfs(i);
}
for(int i = 1; i <= n; i++) {
if(bl[i]) continue;
if(p[i] == i) {
bool ok = 1;
for(int j : g[i]) {
if(get(j) != i) {
ok = 0;
}
}
if(ok) ans.push_back((int)st[i].size());
}
}
out();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
o = clock();
int t = 1;
// cin >> t;
while(t--) {
test();
}
// cout << (clock() - o) * 1.0 / CLOCKS_PER_SEC;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 14
Accepted
time: 3ms
memory: 16232kb
input:
53768 10 50 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
1 10
result:
ok 2 lines
Test #2:
score: 0
Runtime Error
input:
10 800 800 WWWWEWWEWW 7 3 7 5 10 6 9 6 5 8 1 10 1 6 6 1 8 9 3 7 1 3 1 4 9 3 4 2 5 4 5 7 8 10 4 6 2 8 7 2 1 5 3 10 9 10 1 7 6 2 1 8 3 4 10 5 3 3 3 9 2 2 6 1 6 5 6 3 7 9 7 5 8 5 4 3 7 6 9 3 4 9 1 2 7 1 3 4 6 10 8 4 4 9 1 2 6 1 4 4 10 6 10 4 1 5 1 8 5 2 1 9 4 10 9 2 7 9 4 1 6 5 1 6 6 10 10 1 3 10 6 4 8...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #9:
score: 0
Runtime Error
input:
10 10 10 NNNNSENESS 3 2 0 0 1 3 2 3 1 2 3 3 2 0 5 2 4 0 5 1 5 1 2 3 0 4 4 0 1 0 5 0 1 0 2 4 2 2 0 3 0 1 0 1 4 0 1 4 1 0 3 5 5 0 2 5 3 0 3 4 5 3 1 0 5 4 4 0 4 4 1 0 2 0 5 4 0 2 3 0 4 2 0 2 3 0 2 5 5 4 3 0 2 0 5 4 5 4 0 5
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
0%