QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#535484#1127. Virus ExperimentWansur0 24ms48736kbC++233.2kb2024-08-28 05:11:432024-08-28 05:11:43

Judging History

This is the latest submission verdict.

  • [2024-08-28 05:11:43]
  • Judged
  • Verdict: 0
  • Time: 24ms
  • Memory: 48736kb
  • [2024-08-28 05:11:43]
  • 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(6256234451);
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int u[901][901], pos[901][901];
bool used[901][901];
unordered_map<int, bool> can[maxn];
int val[maxn], p[maxn];
int sz[maxn], w[maxn];
int n, m, k;

int get(int x){
    if(p[x] == x) return x;
    return p[x] = get(p[x]);
}

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;
        p[i] = i;
    }

    reverse(t.begin(), t.end());
    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;
        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(p[pos[x1][y1]] < i){
                            p[tx] = p[pos[x1][y1]];
                            break;
                        }
                        q.push({x1, y1});
                    }
                }
            }
            if(p[tx] != tx) break;
        }

        if(p[pos[i][j]] == pos[i][j]){
            int sz = ord.size(), c = 0;
            for(auto [x, y]:ord){
                if(get(pos[x][y]) == tx) c++;
            }
            if(mx > sz){
                mx = sz;
                cnt = 0;
            }
            if(mx == sz) cnt += c;
        }
        for(int x=1;x<=n;x++){
            for(int y=1;y<=m;y++){
                used[x][y] = 0;
            }
        }
    }

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

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: 0
Wrong Answer

Test #9:

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

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

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 6
Accepted
time: 24ms
memory: 48736kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

27
27

result:

ok 2 lines

Test #12:

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

input:

100000 10 10
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
16

result:

ok 2 lines

Test #13:

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

input:

100000 1 1
WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...

output:

1
1

result:

ok 2 lines

Test #14:

score: 0
Wrong Answer
time: 21ms
memory: 46632kb

input:

100000 50 50
ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...

output:

16
16

result:

wrong answer 1st lines differ - expected: '2500', found: '16'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%