QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#811158 | #1127. Virus Experiment | _8_8_ | 0 | 958ms | 493240kb | C++23 | 5.7kb | 2024-12-12 15:57:04 | 2024-12-12 15:57:05 |
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<vector<int>> w[N];
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;
vector<int> nv;
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) {
nv.push_back(conv(kx, ky));
} else {
ok = 0;
}
}
}
if(!ok) continue;
w[conv(x, y)].push_back(nv);
}
}
}
n = r * c;
}
bool is[N];
int p[N], pr[N], bfc[N];
vector<vector<int>> g;
int us[N], timer, m, sn[N];
bool del[N];
void make(int tc) {
timer++;
for(int i = 1; i <= n; i++) {
bfc[i] = 0;
sn[i]= 0;
}
int aa = 0;
for(int i = 1; i <= n; i++) {
if(bl[i]) continue;
for(auto ve : w[i]) {
int lst = -1;
for(int j : ve) {
if(lst == -1) {
lst = p[j];
} else {
if(lst != p[j]) {
lst = -2;
break;
}
}
}
if(lst == -2) continue;
if(lst == p[i]) continue;
if(is[lst] && pr[p[i]] != lst) {
if(us[lst] != timer) {
us[lst] = timer;
g[lst].push_back(p[i]);
}
} else {
g[lst].push_back(p[i]);
}
}
}
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;
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 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);
int 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
Time Limit Exceeded
Test #1:
score: 14
Accepted
time: 7ms
memory: 20492kb
input:
53768 10 50 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
1 10
result:
ok 2 lines
Test #2:
score: 14
Accepted
time: 868ms
memory: 414504kb
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:
1 230450
result:
ok 2 lines
Test #3:
score: 14
Accepted
time: 958ms
memory: 493240kb
input:
10 800 800 WWWWWWWWWW 15314 11896 14475 25269 31478 32227 37443 24837 1353 32232 8163 3206 34713 17755 6870 20331 29572 19341 12557 36054 14768 990 30502 32464 15439 17070 15514 32216 37546 25514 27706 3028 26652 17247 13171 40866 36133 9550 22005 24048 33764 25331 12936 27462 27217 33096 19096 3919...
output:
1 800
result:
ok 2 lines
Test #4:
score: 14
Accepted
time: 938ms
memory: 492112kb
input:
31 800 800 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1 800
result:
ok 2 lines
Test #5:
score: 14
Accepted
time: 330ms
memory: 259228kb
input:
9999 800 800 WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...
output:
1 639810
result:
ok 2 lines
Test #6:
score: 14
Accepted
time: 0ms
memory: 22320kb
input:
10 800 1 EWEWWWWWWW 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 ...
output:
1 392
result:
ok 2 lines
Test #7:
score: 0
Time Limit Exceeded
input:
100000 800 800 WWEEWEEWEEEWEEWWWWWEEEWWWEEEWEWWEWEEEWWWEEEWEWWWWEEWWEWEEEEEEWWEEEWWWWWWWEWWWEEWWWWWWEEWEWEWEEWEWEWEWWEEEEWEEEEWEWWWWEEEEWWWEWWWEWWEWEWWWEWEWEWWEEEEEEWEEEEEWEEEEEWEEEWEEEEEEEWEWWWEWWWEWWWWEEWWEWEEEWWWWEEEEEEWWWEEEEEWEWEWWEWEEEEEEEWEEWWEWWEEWWEEEEEWWEWEWEEWWEEWEEWEWWWWEEWEWEWEEEEEEEWEW...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 6
Accepted
time: 0ms
memory: 22140kb
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
result:
ok 2 lines
Test #10:
score: 6
Accepted
time: 0ms
memory: 20440kb
input:
100000 10 10 NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...
output:
1 10
result:
ok 2 lines
Test #11:
score: 6
Accepted
time: 4ms
memory: 22984kb
input:
100000 11 11 SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...
output:
27 27
result:
ok 2 lines
Test #12:
score: 6
Accepted
time: 0ms
memory: 22420kb
input:
100000 10 10 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
1 16
result:
ok 2 lines
Test #13:
score: 6
Accepted
time: 7ms
memory: 20692kb
input:
100000 1 1 WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...
output:
1 1
result:
ok 2 lines
Test #14:
score: 6
Accepted
time: 18ms
memory: 21116kb
input:
100000 50 50 ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...
output:
2500 2500
result:
ok 2 lines
Test #15:
score: 6
Accepted
time: 0ms
memory: 18076kb
input:
100 10 10 NENNWNSNNEWNENENNWWNEWNSNWWSSSNSNESSESWESSNNNNEWSWESNSNWSENWNSESNENWSWEWWWNSNWNWESNSESENNWNNWSSWSNSE 2 1 4 1 4 2 1 3 2 4 1 4 4 4 3 3 4 2 2 1 1 3 1 4 2 2 1 4 2 2 2 3 4 3 3 3 1 2 4 1 2 2 3 4 3 4 4 1 3 4 1 4 4 3 4 4 1 4 4 2 1 4 3 4 1 1 3 3 4 3 4 4 1 2 3 3 2 3 4 4 2 4 2 1 1 3 4 2 4 4 2 1 2 3 4...
output:
1 1
result:
ok 2 lines
Test #16:
score: 0
Wrong Answer
time: 3ms
memory: 18656kb
input:
100000 50 2 ESNNNSWNNESEWSWWWSENWENSWSNSENSWSENWWNEENNWWNESWNWSEWSWWNSSWSSNENSWWWEEEEENSNWWNNESEWSSNSEEENWWNWWNEENSENWSWEWWNNWWNESSSNWNWWSEWEESESNEEEWNNWWEEEESWSEWWNNSNENWWSEEWNWSNWWEEWNSNWWWWWNWWNNSENNEWSEWENSSSSNWSSSNWSNSNEWESEESWWSEEWWWNWWNESNSNSSNEEWSSENNNEEENSNEEEESNSWNNESEENNEESNSSWENSWSWSNSEE...
output:
45 45
result:
wrong answer 1st lines differ - expected: '46', found: '45'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%