QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#816011#1127. Virus Experiment_8_8_0 0ms22176kbC++234.9kb2024-12-15 20:49:402024-12-15 20:49:42

Judging History

This is the latest submission verdict.

  • [2024-12-15 20:49:42]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 22176kb
  • [2024-12-15 20:49:40]
  • 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]};
                    }
                }
            }
        }
    }
    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);
                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;
        // cout << j << ' ' << pr[j] << ' ' << comp[j] << '\n';
        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
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 22176kb

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

20
20

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 21996kb

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
17

result:

wrong answer 2nd lines differ - expected: '33', found: '17'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%