QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#535482#1127. Virus ExperimentWansur6 23ms46808kbC++233.3kb2024-08-28 05:05:512024-08-28 05:05:51

Judging History

This is the latest submission verdict.

  • [2024-08-28 05:05:51]
  • Judged
  • Verdict: 6
  • Time: 23ms
  • Memory: 46808kb
  • [2024-08-28 05:05:51]
  • Submitted

answer

#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
//#define int long long

using namespace std;
typedef long long ll;
const int maxn = 640000 + 12;

mt19937 rng(9471893);
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int u[901][901], pos[901][901];
bool used[901][901];
map<int, bool> can[maxn];
int val[maxn], p[maxn];
int sz[maxn], w[maxn];
int n, m, k;

void solve(){
    string s;
    cin >> k >> n >> m;
    cin >> s;

    val['W'] = 0;
    val['E'] = 1;
    val['N'] = 2;
    val['S'] = 3;
    while(s.size() <= 1e5){
        s += s;
    }

    for(int mask = 0;mask < 16; mask++){
        for(int i=0;i<s.size();i++){
            if(!(mask & (1 << val[s[i]]))) continue;
            int j = i;
            while(j + 1 < s.size() && (mask & (1 << val[s[j+1]]))){
                j++;
            }
            val[mask] = max(val[mask], j - i + 1);
            i = j;
        }
    }

    vector<pair<int, int>> t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> u[i][j];
            t.push_back({i, j});
        }
    }
    shuffle(t.begin(), t.end(), rng);
    for(int i=1;i<=n*m;i++){
        pos[t[i-1].f][t[i-1].s] = i;
    }

    int mx = 1e9, cnt = 0;
    for(auto [i, j]:t){
        if(!u[i][j]) continue;
        queue<pair<int, int>> q;
        q.push({i, j});
        used[i][j] = 1;
        p[pos[i][j]] = pos[i][j];
        int s = 0, tx = pos[i][j];

        vector<pair<int, int>> ord;

        while(q.size()){
            auto [x, y] = q.front();
            ord.push_back({x, y});
            q.pop();
            s++;

            for(int i=0;i<4;i++){
                int x1 = x + dx[i], y1 = y + dy[i];
                if(!used[x1][y1] && min(x1, y1) > 0 && x1 <= n && y1 <= m && u[x1][y1]){
                    int mask = 0;
                    for(int j=0;j<4;j++){
                        int x2 = x1 + dx[j], y2 = y1 + dy[j];
                        if(used[x2][y2]) mask |= (1 << j);
                    }
                    if(val[mask] >= u[x1][y1]){
                        used[x1][y1] = 1;
                        if(pos[x1][y1] < tx){
                            p[tx] = p[pos[x1][y1]];
                            break;
                        }
                        q.push({x1, y1});
                    }
                }
            }
            if(p[tx] != tx) break;
        }

        if(p[pos[i][j]] == pos[i][j]){
            for(auto [x, y]:ord){
                can[pos[i][j]][pos[x][y]] = 1;
                sz[pos[i][j]]++;
            }
        }
        for(int x=1;x<=n;x++){
            for(int y=1;y<=m;y++){
                used[x][y] = 0;
            }
        }
    }

    reverse(t.begin(), t.end());
    for(auto [i, j]:t){
        if(!u[i][j]) continue;
        if(can[p[pos[i][j]]].count(pos[i][j])) w[p[pos[i][j]]]++;
        if(p[pos[i][j]] == pos[i][j]){
            if(mx > sz[pos[i][j]]){
                mx = sz[pos[i][j]];
                cnt = 0;
            }
            if(mx == sz[pos[i][j]]) cnt += w[p[pos[i][j]]];
        }
    }

    cout << mx << ent << cnt << ent;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 14
Accepted
time: 11ms
memory: 44684kb

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 0
Time Limit Exceeded

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:


result:


Subtask #2:

score: 6
Accepted

Test #9:

score: 6
Accepted
time: 10ms
memory: 44696kb

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: 4ms
memory: 44660kb

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 6
Accepted
time: 13ms
memory: 44724kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

27
27

result:

ok 2 lines

Test #12:

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

input:

100000 10 10
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
16

result:

ok 2 lines

Test #13:

score: 6
Accepted
time: 15ms
memory: 44888kb

input:

100000 1 1
WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...

output:

1
1

result:

ok 2 lines

Test #14:

score: 6
Accepted
time: 16ms
memory: 44844kb

input:

100000 50 50
ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...

output:

2500
2500

result:

ok 2 lines

Test #15:

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

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: 17ms
memory: 44656kb

input:

100000 50 2
ESNNNSWNNESEWSWWWSENWENSWSNSENSWSENWWNEENNWWNESWNWSEWSWWNSSWSSNENSWWWEEEEENSNWWNNESEWSSNSEEENWWNWWNEENSENWSWEWWNNWWNESSSNWNWWSEWEESESNEEEWNNWWEEEESWSEWWNNSNENWWSEEWNWSNWWEEWNSNWWWWWNWWNNSENNEWSEWENSSSSNWSSSNWSNSNEWESEESWWSEEWWWNWWNESNSNSSNEEWSSENNNEEENSNEEEESNSWNNESEENNEESNSSWENSWSWSNSEE...

output:

46
46

result:

ok 2 lines

Test #17:

score: 6
Accepted
time: 6ms
memory: 46752kb

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: 4ms
memory: 44720kb

input:

100000 10 10
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

1
10

result:

ok 2 lines

Test #19:

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

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

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: 9ms
memory: 44956kb

input:

100000 50 50
WWSNNSSSSSSSWWWSWSNNNNSSNNSSNWWNSSNNNSSSSWSWWSNNSNWSNWNWNWSSWWNWWNNSWWSSSWSNWNWSWWNNNNWSSSNSSNNNSSSNSWSWSWWWWSSNNNSWNSNSSSWSWNNWNSNNWSNWSSSWSWWSWNWSWWNNNSSWWSNWSWSNWNNWNSNSSSNNNNWNSWWWNNSWNWWNNSWWNNWNWSNSSWNWNWWWSNSWSNWNSWSWSNWNNNWNSNSSWWNSNWSWNWNSWNNSSWNSNNWSNSWWWWSSWSNNNNSSWWWWNSWNWSW...

output:

50
50

result:

ok 2 lines

Test #22:

score: 6
Accepted
time: 15ms
memory: 44668kb

input:

100000 50 50
SWSSSNWSNWNNNSNSSSNNSWNNWNWWNSNNNSNNWNNSNWNWSNSWWNSWWNSSWNWNWSWNNSSNNWSWSNNNNWWSNSSSSWSSWWSNNWWSNNWSSSSSSWNNWSWWSWWWWNSNSNWWWSSWWNNSSWSNWNSNSNNSWSWWWNSWWNSNSSNSWSNNSWNWSSNWWSSSNWNWSWSNSNSSWWNNWWWWNNNSWWWNWWNSWWNNWSNNSNNWNSSNWWNNSSNSSNSSSNWSNSSWWWNNNSSWSWNNSNSNWSNSNSSWSSSSWSWNNNNWSWWSNNW...

output:

1
3

result:

ok 2 lines

Test #23:

score: 6
Accepted
time: 18ms
memory: 44668kb

input:

100000 50 50
NNEENENWWNWNNEEWNNWWWWNENNWWNENWNNWNNWWENEENNNEEEWENEENENWNEEEENNEWEWEWNNWNNNEWNWEWNNENWWWWWEENNNNENWWWNENNENENWENNWNWEEEEEWNWWWEWWEWENEENNWEEWWWEEENWNNEENEEEEEWWWWEEEEWWWEEEEWWNNNNEEEWNEWEWENEWEWNEEWNWENWNWEWENNENNWNWEWWENNEWNNNNNNNENNENNNNWEENNNWWWWNNENEEEWNWNWEWNNWNNENWWWWNWNEENWWWEN...

output:

50
50

result:

ok 2 lines

Test #24:

score: 6
Accepted
time: 23ms
memory: 44692kb

input:

100000 50 50
SESWSSWEWEWSWESWEEEWESESSEWEWWSEEEWSESEWSESWWSWEWSSSWSEWESSWSSWSWWWWESEEWEWEWEEEWEEEWWSEEESSEESEEWSESSWEEEWWWSEWSWWSEWSWWEESSWSEEEEEWSSWEWEEESEEWSSWSEWESEWSSEWWSWEWSWESESEEWEEEWESWEESWSESWWSWSWEWESWESEESESSWSESESESSEEWWSSWESEWSWSSSEWWWWSSESSSEESSWWWSEWSSSSESWSSSSEESWSSEWSSSEEESWESWSEEWE...

output:

1
37

result:

ok 2 lines

Test #25:

score: 6
Accepted
time: 19ms
memory: 44680kb

input:

50000 50 49
SNNWEENNESEEEWSESNWSENSSWNWWENENWWEWSEWEEENSNSWEEEESENEEENNSSSESSNEEWSWEWWNSSWNNNSNNNWSSSNEWSSSESWSSWNSSESSNESESWESSWWSEENWENWWENWEWWNNWNWNWEESSSEWWSSSWNSEESWEENNENWEWNNEESSNWSNWSWWWSENWSESSNNNSESNESNSNSWSSNNSNWWEEESESSNNESSWNEENWEESESWSNWNENWNENEEENNSEEESEWENSESWENENSENSWNEEEEWNNSWNNSNN...

output:

3
915

result:

ok 2 lines

Test #26:

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

input:

2000 50 50
NNWSNWWSWNNSNWNNNENWNSWSENSWWSNWNWSSSWNESNSWSENWSNWWSWWENWSWNENWSWENSSSSWNWSNWESWNSNWESSEEEEEESNWNNESENNWNNESNSWNNNNESSWNNENEWSNESSNWNNENEEWWEWNEWNSSWSSSEWEESSNEWSEWNSSSWWSNEWEEWESENNSNSNWSWWENNWNSWSWNESEWNEWESWESSESWNEWNESNNWESSSSENSSSESNWNSNWSNNSESESSSNWNEEWNWSNNWEEWSEWEENSNWSESSESEWENN...

output:

50
1400

result:

ok 2 lines

Test #27:

score: 6
Accepted
time: 16ms
memory: 46808kb

input:

100000 50 50
NNNNSENESSEEWWNSESWWNNEEWSEWSEWNWNEESWNEENWWNNWWEWWNNENNWSWSNNEENWSNSSNSNSSNSSWESWEWSWWSENWNWSENWWWSSESENNWNNWESNWEEESNESSWEWSSNESSEEEEWEWESNSNWEEWNWNSENSSNNESEEWESENENESSNNSWWEWWNWNEWENSNWENWEENNNSWSENWWSWENNWSESNSNSWSSSENSSSENNWWEESENSSNESNNSESNNWNWNEESEWWSEWWESEWSEEWWSSNENSNWWSNEENEW...

output:

1
2262

result:

ok 2 lines

Subtask #3:

score: 0
Skipped

Dependency #1:

0%