QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#816017#1127. Virus Experiment_8_8_6 628ms58420kbC++235.0kb2024-12-15 20:55:152024-12-15 20:55:23

Judging History

This is the latest submission verdict.

  • [2024-12-15 20:55:23]
  • Judged
  • Verdict: 6
  • Time: 628ms
  • Memory: 58420kb
  • [2024-12-15 20:55:15]
  • 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], 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]};
                    }
                }
            }
        }
    }
    for(int f : sn) {
        msk[f] = 0;
    }
    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);
                vis[comp[j]] =  i + 1;
                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;
        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
Time Limit Exceeded

Test #1:

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

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 14
Accepted
time: 628ms
memory: 57256kb

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: 97ms
memory: 56964kb

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: 108ms
memory: 58420kb

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: 0
Time Limit Exceeded

input:

9999 800 800
WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...

output:


result:


Subtask #2:

score: 6
Accepted

Test #9:

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

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: 3ms
memory: 22408kb

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 6
Accepted
time: 7ms
memory: 22928kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

27
27

result:

ok 2 lines

Test #12:

score: 6
Accepted
time: 3ms
memory: 22408kb

input:

100000 10 10
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
16

result:

ok 2 lines

Test #13:

score: 6
Accepted
time: 3ms
memory: 18640kb

input:

100000 1 1
WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...

output:

1
1

result:

ok 2 lines

Test #14:

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

input:

100000 50 50
ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...

output:

2500
2500

result:

ok 2 lines

Test #15:

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

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: 6
Accepted
time: 3ms
memory: 24780kb

input:

100000 50 2
ESNNNSWNNESEWSWWWSENWENSWSNSENSWSENWWNEENNWWNESWNWSEWSWWNSSWSSNENSWWWEEEEENSNWWNNESEWSSNSEEENWWNWWNEENSENWSWEWWNNWWNESSSNWNWWSEWEESESNEEEWNNWWEEEESWSEWWNNSNENWWSEEWNWSNWWEEWNSNWWWWWNWWNNSENNEWSEWENSSSSNWSSSNWSNSNEWESEESWWSEEWWWNWWNESNSNSSNEEWSSENNNEEENSNEEEESNSWNNESEENNEESNSSWENSWSWSNSEE...

output:

46
46

result:

ok 2 lines

Test #17:

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

input:

100 47 41
WWENEWENESSWWNESSENWNEWESWNWESNWNWSEWNEWNSWENSWSNNSWWNNENEWNWWWSWSSESSNEEWEENWEWNWENENESEENNWWWNSWEW
1 2 1 1 2 10 1 2 1 1 2 8 2 2 1 1 1 8 1 1 1 2 2 9 2 1 1 1 1 9 2 1 2 2 2 9 1 2 2 2 2
1 1 1 2 1 9 1 2 2 2 2 9 2 1 2 2 2 9 2 1 1 2 1 9 1 1 1 2 1 8 1 2 2 1 1 10 2 2 2 1 1
2 2 1 2 10 1 2 2 1 1 10...

output:

28
56

result:

ok 2 lines

Test #18:

score: 6
Accepted
time: 3ms
memory: 22448kb

input:

100000 10 10
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

1
10

result:

ok 2 lines

Test #19:

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

input:

10 50 50
ESSSSSSSEE
4 2 10 7 7 1 8 1 2 4 8 4 4 2 9 7 3 9 7 3 9 3 4 6 7 2 5 2 4 8 5 2 2 10 10 6 2 1 1 5 10 7 3 10 10 10 6 8 7 7
9 3 9 6 1 7 10 9 8 7 2 1 10 8 4 4 10 8 10 5 2 7 6 6 3 10 2 4 1 3 3 2 8 3 9 1 7 2 3 8 7 7 1 5 3 7 5 2 10 5
1 2 10 1 1 4 1 5 1 10 10 10 10 2 7 5 1 8 8 5 5 3 4 5 1 3 5 6 1 6 8 ...

output:

1
545

result:

ok 2 lines

Test #20:

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

input:

100 50 50
WWWNSWNWWESSSESNEWESENENWESESSEENNWNWNSWESENEEEESWEENWSWWWWNEENEEWSSWNWNWNEESEEENWENSENSESSSWNWSSNSW
1 1 2 1 2 1 1 2 1 2 2 1 2 2 2 1 1 2 2 2 1 8 2 1 2 2 2 1 2 1 1 2 2 2 1 1 1 1 2 1 1 2 1 1 1 2 1 2 2 2
1 2 1 1 1 2 2 1 1 2 2 1 2 1 2 1 2 1 1 1 2173 2 2 1 1 2 1 2 1 2 1 1 2 2 2 2 1 1 1 1 1 1 1 ...

output:

2500
2500

result:

ok 2 lines

Test #21:

score: 6
Accepted
time: 3ms
memory: 22688kb

input:

100000 50 50
WWSNNSSSSSSSWWWSWSNNNNSSNNSSNWWNSSNNNSSSSWSWWSNNSNWSNWNWNWSSWWNWWNNSWWSSSWSNWNWSWWNNNNWSSSNSSNNNSSSNSWSWSWWWWSSNNNSWNSNSSSWSWNNWNSNNWSNWSSSWSWWSWNWSWWNNNSSWWSNWSWSNWNNWNSNSSSNNNNWNSWWWNNSWNWWNNSWWNNWNWSNSSWNWNWWWSNSWSNWNSWSWSNWNNNWNSNSSWWNSNWSWNWNSWNNSSWNSNNWSNSWWWWSSWSNNNNSSWWWWNSWNWSW...

output:

50
50

result:

ok 2 lines

Test #22:

score: 6
Accepted
time: 3ms
memory: 22932kb

input:

100000 50 50
SWSSSNWSNWNNNSNSSSNNSWNNWNWWNSNNNSNNWNNSNWNWSNSWWNSWWNSSWNWNWSWNNSSNNWSWSNNNNWWSNSSSSWSSWWSNNWWSNNWSSSSSSWNNWSWWSWWWWNSNSNWWWSSWWNNSSWSNWNSNSNNSWSWWWNSWWNSNSSNSWSNNSWNWSSNWWSSSNWNWSWSNSNSSWWNNWWWWNNNSWWWNWWNSWWNNWSNNSNNWNSSNWWNNSSNSSNSSSNWSNSSWWWNNNSSWSWNNSNSNWSNSNSSWSSSSWSWNNNNWSWWSNNW...

output:

1
3

result:

ok 2 lines

Test #23:

score: 6
Accepted
time: 5ms
memory: 22924kb

input:

100000 50 50
NNEENENWWNWNNEEWNNWWWWNENNWWNENWNNWNNWWENEENNNEEEWENEENENWNEEEENNEWEWEWNNWNNNEWNWEWNNENWWWWWEENNNNENWWWNENNENENWENNWNWEEEEEWNWWWEWWEWENEENNWEEWWWEEENWNNEENEEEEEWWWWEEEEWWWEEEEWWNNNNEEEWNEWEWENEWEWNEEWNWENWNWEWENNENNWNWEWWENNEWNNNNNNNENNENNNNWEENNNWWWWNNENEEEWNWNWEWNNWNNENWWWWNWNEENWWWEN...

output:

50
50

result:

ok 2 lines

Test #24:

score: 6
Accepted
time: 3ms
memory: 24752kb

input:

100000 50 50
SESWSSWEWEWSWESWEEEWESESSEWEWWSEEEWSESEWSESWWSWEWSSSWSEWESSWSSWSWWWWESEEWEWEWEEEWEEEWWSEEESSEESEEWSESSWEEEWWWSEWSWWSEWSWWEESSWSEEEEEWSSWEWEEESEEWSSWSEWESEWSSEWWSWEWSWESESEEWEEEWESWEESWSESWWSWSWEWESWESEESESSWSESESESSEEWWSSWESEWSWSSSEWWWWSSESSSEESSWWWSEWSSSSESWSSSSEESWSSEWSSSEEESWESWSEEWE...

output:

1
37

result:

ok 2 lines

Test #25:

score: 6
Accepted
time: 3ms
memory: 26720kb

input:

50000 50 49
SNNWEENNESEEEWSESNWSENSSWNWWENENWWEWSEWEEENSNSWEEEESENEEENNSSSESSNEEWSWEWWNSSWNNNSNNNWSSSNEWSSSESWSSWNSSESSNESESWESSWWSEENWENWWENWEWWNNWNWNWEESSSEWWSSSWNSEESWEENNENWEWNNEESSNWSNWSWWWSENWSESSNNNSESNESNSNSWSSNNSNWWEEESESSNNESSWNEENWEESESWSNWNENWNENEEENNSEEESEWENSESWENENSENSWNEEEEWNNSWNNSNN...

output:

3
915

result:

ok 2 lines

Test #26:

score: 6
Accepted
time: 5ms
memory: 22176kb

input:

2000 50 50
NNWSNWWSWNNSNWNNNENWNSWSENSWWSNWNWSSSWNESNSWSENWSNWWSWWENWSWNENWSWENSSSSWNWSNWESWNSNWESSEEEEEESNWNNESENNWNNESNSWNNNNESSWNNENEWSNESSNWNNENEEWWEWNEWNSSWSSSEWEESSNEWSEWNSSSWWSNEWEEWESENNSNSNWSWWENNWNSWSWNESEWNEWESWESSESWNEWNESNNWESSSSENSSSESNWNSNWSNNSESESSSNWNEEWNWSNNWEEWSEWEENSNWSESSESEWENN...

output:

50
1400

result:

ok 2 lines

Test #27:

score: 6
Accepted
time: 12ms
memory: 28976kb

input:

100000 50 50
NNNNSENESSEEWWNSESWWNNEEWSEWSEWNWNEESWNEENWWNNWWEWWNNENNWSWSNNEENWSNSSNSNSSNSSWESWEWSWWSENWNWSENWWWSSESENNWNNWESNWEEESNESSWEWSSNESSEEEEWEWESNSNWEEWNWNSENSSNNESEEWESENENESSNNSWWEWWNWNEWENSNWENWEENNNSWSENWWSWENNWSESNSNSWSSSENSSSENNWWEESENSSNESNNSESNNWNWNEESEWWSEWWESEWSEEWWSSNENSNWWSNEENEW...

output:

1
2262

result:

ok 2 lines

Subtask #3:

score: 0
Skipped

Dependency #1:

0%