QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#815882#1127. Virus Experiment_8_8_0 7ms16232kbC++235.7kb2024-12-15 18:23:142024-12-15 18:23:15

Judging History

This is the latest submission verdict.

  • [2024-12-15 18:23:15]
  • Judged
  • Verdict: 0
  • Time: 7ms
  • Memory: 16232kb
  • [2024-12-15 18:23:14]
  • 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], p[N];
string s;
vector<int> w[N], st[N];
int o;
int conv(int x, int y) {
    return (x - 1) * c + y;
}
bool bl[N];
int lst_a = -1;
pair<int, int> ob[N];
vector<int> g[N];
set<int> rts;
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;
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        st[i].push_back(i);
        rts.insert(i);
        for(int j : w[i]) {
            if(__builtin_popcount(j) == 1) {
                for(int k = 0; k < 4; k++) {
                    if((j >> k) & 1) {
                        int kx = ob[i].first - dx[k], ky = ob[i].second - dy[k];
                        g[conv(kx, ky)].push_back(i);
                        // cout << conv(kx, ky) << ' ' << i << ' ' << j << '\n';
                        break;
                    }
                }
            }
        }
    }
}
vector<int> ans;

void out() {
    sort(ans.begin(), ans.end());
    int res = 0;
    for(int i = 0; i < (int)ans.size() && ans[i] == ans[0]; i++) {
        res += ans[i];
    }
    cout << ans[0] << '\n' << res << '\n';
}
int get(int v) {
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
bool check(int i, int f) {
    for(int j : w[i]) {
        bool ok = 1;
        for(int k = 0; k < 4; k++) {
            if((j >> k) & 1) {
                int x = ob[i].first - dx[k], y = ob[i].second - dy[k];
                assert(x >= 1 && x <= r && y >= 1 && y <= c);
                if(get(conv(x, y)) != f) {
                    ok = 0;
                    break;
                }
            }
        }
        if(ok) return 1;
    }
    return 0;
}
void merge(int v, int u) {
    v = get(v);
    u = get(u);
    p[v] = u;
    for(int i : g[v]) {
        i = get(i);
        if(i == u) continue;
        g[u].push_back(i);
    }
    for(int i : st[v]) {
        st[u].push_back(i);
        for(int j = 0; j < 4; j++) {
            int x = dx[j] + ob[i].first, y = dy[j] + ob[i].second;
            if(x >= 1 && x <= r && y >= 1 && y <= c) {
                if(get(conv(x, y)) == u) continue;
                if(check(conv(x, y), u)) {
                    // if(u == 1)cout << u << ' ' << conv(x, y) << "x\n";
                    g[u].push_back(conv(x, y));
                }
            }
        }
    }
}
int vis[N];
vector<int> pa;
void dfs(int v) {
    vis[v] = 1;
    pa.push_back(v);
    bool is = 0;
    // cout << v << '\n';
    for(int it = 0; it < (int)g[v].size(); it++) {
        int to = g[v][it];
        to = get(to);
        if(to == v) continue;
        if(vis[to] == 1) {
            is = 1;
            while(!pa.empty() && pa.back() != to) {
                int x = pa[(int)pa.size() - 1], y = pa[(int)pa.size() - 2];
                merge(y, x);
                pa.pop_back();
            }
            pa.pop_back();
            pa.push_back(get(to));
            assert(v == get(v));
            // v = get(v);
        } else if(!vis[to]) {
            dfs(to);
            if(v != get(v)) break;
        }
    }
    vis[v] = 2;
    pa.pop_back();
}
void test() {
    cin >> n >> r >> c;
    prec();
    for(int i = 1; i <= n; i++) {
        if(bl[i] || get(i) != i) continue;
        dfs(i);
    }
    for(int i = 1; i <= n; i++) {
        if(bl[i]) continue;
        if(p[i] == i) {
            bool ok = 1;
            for(int j : g[i]) {
                if(get(j) != i) {
                    ok = 0;
                }
            }
            if(ok) ans.push_back((int)st[i].size());
        }
    }
    if(!ans.empty()) out();
}

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;
}   

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

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

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 0
Runtime Error

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
Runtime Error

Test #9:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%