QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#816011 | #1127. Virus Experiment | _8_8_ | 0 | 0ms | 22176kb | C++23 | 4.9kb | 2024-12-15 20:49:40 | 2024-12-15 20:49:42 |
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], pr[N], comp[N];
string s;
int o;
int conv(int x, int y) {
return (x - 1) * c + y;
}
bool bl[N], w[N][16], is[N];
pair<int, int> ob[N];
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)][i] = 1;
}
}
}
n = r * c;
for(int i = 1; i <= n; ++i) {
pr[i] = comp[i] = i;
}
}
inline bool in(int x, int y) {
return (x >= 1 && x <= r && y >= 1 && y <= c);
}
int msk[N], us[N], timer;
pair<int, int> bfs(int j) {
timer++;
queue<int> q;
us[j] = timer;
q.push(j);
vector<int> sn;
while(!q.empty()) {
int v = q.front();
q.pop();
auto [x, y] = ob[v];
for(int i = 0; i < 4; i++) {
int kx = x + dx[i], ky = y + dy[i];
if(in(kx, ky)) {
int to = conv(kx, ky);
if(us[to] == timer) continue;
if(!msk[to]) {
sn.push_back(to);
}
msk[to] |= (1 << i);
if(w[to][msk[to]]) {
if(pr[to] == comp[j]) {
us[to] = timer;
comp[to] = comp[v];
q.push(to);
} else {
for(int f : sn) {
msk[f] = 0;
}
return {comp[j], pr[to]};
}
}
}
}
}
return {-1, -1};
}
int vis[N], P[N];
pair<int, int> ed[N];
int get(int v) {
if(P[v] == v) return v;
return P[v] = get(P[v]);
}
void merge(int v, int u) {
v = get(v);
u = get(u);
P[v] = u;
}
int col[N];
void test() {
cin >> n >> r >> c;
prec();
for(int i = 0; i < 20; i++) {
for(int j = 1; j <= n; j++) {
P[j] = j;
}
int it = 0;
for(int j = 1; j <= n; ++j) {
if(bl[j]) continue;
if(vis[comp[j]] != i + 1 && pr[j] == comp[j]) {
auto [x, y] = bfs(j);
if(x != -1) {
ed[it++] = {x, y};
}
}
}
for(int j = 0; j < it; j++) {
merge(ed[j].first, ed[j].second);
}
for(int j = 1; j <= n; j++) {
pr[j] = get(pr[j]);
}
}
for(int j = 1; j <= n; j++) {
if(bl[j]) continue;
// cout << j << ' ' << pr[j] << ' ' << comp[j] << '\n';
if(pr[j] == comp[j]) {
col[pr[j]]++;
}
}
vector<int> x;
for(int i = 1; i <= n; i++) {
if(col[i]) {
x.push_back(col[i]);
}
}
sort(x.begin(), x.end());
int res = 0;
for(int i = 0; i < (int)x.size() && x[i] == x[0]; i++) {
res += x[i];
}
cout << x[0] << '\n' << res << '\n';
}
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;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 22176kb
input:
53768 10 50 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
20 20
result:
wrong answer 1st lines differ - expected: '1', found: '20'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 21996kb
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:
1 17
result:
wrong answer 2nd lines differ - expected: '33', found: '17'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%