QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#815946#1127. Virus Experiment_8_8_14 513ms259088kbC++236.8kb2024-12-15 19:26:162024-12-15 19:26:17

Judging History

This is the latest submission verdict.

  • [2024-12-15 19:26:17]
  • Judged
  • Verdict: 14
  • Time: 513ms
  • Memory: 259088kb
Show
  • [2024-12-15 19:26:16]
  • Submitted

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;
vector<int> w[N];
int o;
int conv(int x, int y) {
    return (x - 1) * c + y;
}
bool bl[N];
bool del[N], bd[N];
int lst_a = -1;
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)].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;

int ve[N];
bool sk[N][16];
int ch = 0;
void make(int tc) {
    timer++;
    for(int i = 1; i <= m; i++) {
        bfc[i] = del[i] = 0;
    }
    ch = 0;
    for(int i = 1; i <= n; i++) {
        if(bl[i] || bd[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) {
                continue;
            }
            if(lst == p[i]) {
                sk[i][f] = 1;
                continue;
            }
            if(is[lst] && pr[p[i]] != lst) {
                if(us[lst] != timer) {
                    us[lst] = timer;
                    del[lst] = 1;
                    g[lst].push_back(p[i]);
                    sk[i][f] = 1;
                    ch = 1;
                } else {
                    // nw.push_back(f);
                }
            } else {
                g[lst].push_back(p[i]);
                del[lst] = 1;
                ch = 1;
                sk[i][f] = 1;
            }
        }
        // w[i].swap(nw);
    }
    for(int i = 1; i <= n; i++) {
        if(!del[p[i]]) {
            bd[i] = 1;
        }
    }
    // 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());
    int t = 0;
    for(int i : ord) {
        if(!bfc[i]) {
            dfs1(i, ++t);
        }
    }
    m = t;
    vector<vector<int>> G(m + 1), GT(m + 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();
    m = n;
    g.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        pr[i] = p[i] = i;
        is[i] = 1;
    }
    ch = 1;
    while(ch) {
        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;
}
源文件, 语言: C++23

詳細信息

Subtask #1:

score: 14
Accepted

Test #1:

score: 14
Accepted
time: 7ms
memory: 26516kb

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 14
Accepted
time: 513ms
memory: 211324kb

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: 389ms
memory: 242004kb

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: 380ms
memory: 241292kb

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: 145ms
memory: 140080kb

input:

9999 800 800
WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...

output:

1
639810

result:

ok 2 lines

Test #6:

score: 14
Accepted
time: 2ms
memory: 26176kb

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: 14
Accepted
time: 452ms
memory: 259088kb

input:

100000 800 800
WWEEWEEWEEEWEEWWWWWEEEWWWEEEWEWWEWEEEWWWEEEWEWWWWEEWWEWEEEEEEWWEEEWWWWWWWEWWWEEWWWWWWEEWEWEWEEWEWEWEWWEEEEWEEEEWEWWWWEEEEWWWEWWWEWWEWEWWWEWEWEWWEEEEEEWEEEEEWEEEEEWEEEWEEEEEEEWEWWWEWWWEWWWWEEWWEWEEEWWWWEEEEEEWWWEEEEEWEWEWWEWEEEEEEEWEEWWEWWEEWWEEEEEWWEWEWEEWWEEWEEWEWWWWEEWEWEWEEEEEEEWEW...

output:

800
640000

result:

ok 2 lines

Test #8:

score: 14
Accepted
time: 69ms
memory: 74508kb

input:

100000 500 500
EWWWEWEWEEWWEEEEEWWEWEEWEWWEEWEEEWEWWWWEWEWWWEWWEWEEWWWWWWWEEEEEEEEEWEEEEEEWEWWEEEEEEEWWEEEWWWEEWWEWEEWWEWWWWWWWWEWEEEWEWWWEWEWWEEEEEEEWWEEEWWWEEWWEEEWEWEWEWWWEWWWEEEWEEWWWWEWWEWWEWWEEEEWWEEWEEEEWEEWWEEEEWWWEWWWEWEWWEWWWEWEEEEEWWWEWEWEEEWWWEEEWEWWWEEWEWEEEWWWWEWEEWWEEWEEEWEWEWWEWEWWWE...

output:

1
227098

result:

ok 2 lines

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 6
Accepted
time: 0ms
memory: 24244kb

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: 26784kb

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 6
Accepted
time: 4ms
memory: 26820kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

27
27

result:

ok 2 lines

Test #12:

score: 6
Accepted
time: 0ms
memory: 26552kb

input:

100000 10 10
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
16

result:

ok 2 lines

Test #13:

score: 6
Accepted
time: 4ms
memory: 24724kb

input:

100000 1 1
WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...

output:

1
1

result:

ok 2 lines

Test #14:

score: 6
Accepted
time: 9ms
memory: 27288kb

input:

100000 50 50
ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...

output:

2500
2500

result:

ok 2 lines

Test #15:

score: 6
Accepted
time: 2ms
memory: 26304kb

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: 12ms
memory: 26820kb

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:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

伺服器時間: 2025-02-08 21:56:26 | 開源專案