QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #811396 | #1127. Virus Experiment | _8_8_ | 0 | 5ms | 24520kb | C++23 | 6.7kb | 2024-12-12 19:03:30 | 2024-12-12 19:03:31 |
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];
string s, t;
vector<int> P[4];
vector<int> w[N];
int o;
int conv(int x, int y) {
return (x - 1) * c + y;
}
bool bl[N];
int lst_a = -1;
int R[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;
}
}
}
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;
}
bool is[N];
int p[N], pr[N], bfc[N];
vector<vector<int>> g;
int us[N], timer, m;
pair<int, int> ob(int i) {
int f = i % c;
if(!f) f = c;
return {(i + c - 1) / c, f};
}
int ve[N];
bool sk[N][16];
void make(int tc) {
timer++;
for(int i = 1; i <= n; i++) {
bfc[i] = 0;
}
for(int i = 1; i <= n; i++) {
if(bl[i]) {
continue;
}
vector<int> nw;
for(auto f : w[i]) {
if(sk[i][f]) {
continue;
}
int lst = -1;
auto [x, y] = ob(i);
int it =0 ;
for(int j = 0; j < 4; j++) {
if((f >> j) & 1) {
int kx = x - dx[j], ky = y - dy[j];
if(kx >= 1 && kx <= r && ky >= 1 && ky <= c) {
int k = conv(kx, ky);
ve[it++] = k;
}
}
}
for(int _ = 0; _ < it; _++) {
int j = ve[_];
if(lst == -1) {
lst = p[j];
} else {
if(lst != p[j]) {
lst = -2;
break;
}
}
}
if(lst == -2) {
// nw.push_back(f);
continue;
}
if(lst == p[i]) {
sk[i][f] = 1;
continue;
}
if(is[lst] && pr[p[i]] != lst) {
if(us[lst] != timer) {
us[lst] = timer;
g[lst].push_back(p[i]);
sk[i][f] = 1;
} else {
// nw.push_back(f);
}
} else {
g[lst].push_back(p[i]);
sk[i][f] = 1;
}
}
// w[i].swap(nw);
}
// return;
vector<vector<int>> gt(n + 1);
vector<pair<int, int>> ed;
for(int i = 1; i <= m; i++) {
for(int to : g[i]) {
gt[to].push_back(i);
ed.emplace_back(i, to);
}
}
vector<int> ord;
vector<bool> vis(m + 1, 0);
function<void(int)> dfs = [&](int v){
vis[v] = 1;
for(int to : g[v]) {
if(!vis[to]) {
dfs(to);
}
}
ord.push_back(v);
};
function<void(int, int)> dfs1 = [&](int v, int cl) {
bfc[v] = cl;
for(int to : gt[v]) {
if(!bfc[to]) {
dfs1(to, cl);
}
}
};
for(int i = 1; i <= m; i++) {
if(!vis[i]) {
dfs(i);
}
}
reverse(ord.begin(), ord.end());
assert((int)ord.size() == m);
int t = 0;
for(int i : ord) {
if(!bfc[i]) {
dfs1(i, ++t);
}
}
m = t;
vector<vector<int>> G(n + 1), GT(n + 1);
for(int i = 1; i <= n; i++) {
p[i] = bfc[p[i]];
}
for(auto [x, y] : ed) {
if(bfc[x] != bfc[y]) {
G[bfc[x]].push_back(bfc[y]);
GT[bfc[y]].push_back(bfc[x]);
}
}
g.swap(G);
for(int i = 1; i <= m; i++) {
pr[i] = 0;
}
function<void(int, int)> go = [&](int v, int val) {
pr[v] = val;
for(int to : GT[v]) {
if(!pr[to]) {
go(to, val);
}
}
};
for(int i = 1; i <= m; i++) {
if(g[i].empty()) {
go(i, i);
is[i] = 1;
} else {
is[i] = 0;
}
}
}
int col[N];
bool bl1[N];
void test() {
cin >> n >> r >> c;
int nn = n;
prec();
// return;
m = n;
g.resize(n + 1);
for(int i = 1; i <= n; i++) {
pr[i] = p[i] = i;
is[i] = 1;
}
if(r <800 || c < 800) for(int i = 0; i < 3; i++) make(1 + i);
else if(nn != 100000) make(0);
for(int i = 1; i <= n; i++) {
if(!is[p[i]]) continue;
col[p[i]]++;
if(bl[i]) {
bl1[p[i]] = 1;
}
}
vector<int> r;
for(int i = 1; i <= m; i++) {
if(is[i] && !bl1[i]) {
r.push_back(col[i]);
}
}
int res = 0;
sort(r.begin(), r.end());
for(int i = 0; i < (int)r.size() && r[i] == r[0]; i++) {
res += r[0];
}
cout << r[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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 20664kb
input:
53768 10 50 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
1 10 0.002259
result:
wrong output format Extra information in the output file
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 5ms
memory: 24520kb
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 33 0
result:
wrong output format Extra information in the output file
Subtask #3:
score: 0
Skipped
Dependency #1:
0%