QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811111#1127. Virus Experiment_8_8_0 65ms20412kbC++206.5kb2024-12-12 15:32:342024-12-12 15:32:39

Judging History

This is the latest submission verdict.

  • [2024-12-12 15:32:39]
  • Judged
  • Verdict: 0
  • Time: 65ms
  • Memory: 20412kb
  • [2024-12-12 15:32:34]
  • 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];
string s, t;
vector<int> P[4];
vector<vector<int>> w[N];

int conv(int x, int y) {
    return (x - 1) * c + y;
}
bool bl[N];
int lst_a = -1;
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;
            }
        }
    }
    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;
        }
        P[e[i]].push_back(i);
    }
    for(int i = 1; i < (1 << 4); i++) {
        vector<int> f;
        for(int j = 0; j < 4; j++) {
            if(!((i >> j) & 1)) {
                for(int j : P[j]) {
                    f.push_back(j);
                }
            }
        }
        int mx = 0;
        if(f.empty()) { 
            mx = (int)1e6;
        } else {
            sort(f.begin(), f.end());
            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;
                vector<int> nv;
                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) {
                            nv.push_back(conv(kx, ky));
                        } else {
                            ok = 0;
                        }
                    }
                }
                if(!ok) continue;
                w[conv(x, y)].push_back(nv);
            }
        }
    }
    n = r * c;
}
bool is[N];
int p[N], pr[N], bfc[N];
vector<vector<int>> g;
int us[N], timer, m, sn[N];
bool del[N];
void make(int tc) {
    timer++;
    for(int i = 1; i <= n; i++) {
        bfc[i] = 0;
        sn[i]= 0;
    }
    int aa = 0;
    for(int i = 1; i <= n; i++) {
        if(bl[i]) continue;
        for(auto ve : w[i]) {
            int lst = -1;
            for(int j : ve) {
                if(lst == -1) {
                    lst = p[j];
                } else {
                    if(lst != p[j]) {
                        lst = -2;
                    }
                }
            }
            if(lst == -2) continue;
            if(lst == p[i]) continue;
            if(is[lst]) {
                assert(pr[lst] == lst);
                if(pr[p[i]] != lst) {
                    if(us[lst] != timer) {
                        us[lst] = timer;
                        g[lst].push_back(p[i]);
                    }
                } 
                else {
                    g[lst].push_back(p[i]);
                    sn[lst] = 1;
                }
            }
        }
    }
    for(int i = 1; i <= m; i++) {
        if(!is[i]) continue;
        if(us[i] == timer || sn[i]) {
            aa++;
        }
    }
    assert(lst_a == -1 || aa <= (lst_a + 1) / 2);
    lst_a = aa;
    for(int i = 1; i <= n; i++) {
        if(!is[p[i]]) continue;
        if(del[i]) {
            assert(us[p[i]] != timer && !sn[p[i]]);
        }
        if(us[p[i]] != timer && !sn[p[i]]) {
            del[i] = 1;
        }
    }
    vector<vector<int>> gt(n + 1);
    vector<pair<int, int>> ed;
    for(int i = 1; i <= m; i++) {
        for(int to : g[i]) {
            gt[to].push_back(i);
            ed.emplace_back(i, to);
        }
    }
    // return;
    vector<int> ord;
    vector<bool> vis(m + 1, 0);
    function<void(int)> dfs = [&](int v){
        vis[v] = 1;
        for(int to : g[v]) {
            if(!vis[to]) {
                dfs(to);
            }
        }
        ord.push_back(v);
    };
    function<void(int, int)> dfs1 = [&](int v, int cl) {
        bfc[v] = cl;
        // if(tc == 2 && cl == 49) {
        //     cout << v << "x\n";
        // }
        for(int to : gt[v]) {
            if(!bfc[to]) {
                dfs1(to, cl);
            }
        }  
    };
    for(int i = 1; i <= m; i++) {
        if(!vis[i]) {
            dfs(i);
        }
    }
    reverse(ord.begin(), ord.end());
    assert((int)ord.size() == m);
    int t = 0;
    for(int i : ord) {
        if(!bfc[i]) {
            dfs1(i, ++t);
        }
    }
    m = t;
    vector<vector<int>> G(n + 1), GT(n + 1);
    for(int i = 1; i <= n; i++) {
        // cout << i << ' ' << p[i] << ' ' << bfc[i] << '\n';
        p[i] = bfc[p[i]];
    }
    for(auto [x, y] : ed) {
        if(bfc[x] != bfc[y]) {
            G[bfc[x]].push_back(bfc[y]);
            GT[bfc[y]].push_back(bfc[x]);
        }
    }
    g = G;
    for(int i = 1; i <= m; i++) {
        pr[i] = 0;
    }
    function<void(int, int)> go = [&](int v, int val) {
        pr[v] = val;
        for(int to : GT[v]) {
            if(!pr[to]) {
                go(to, val);
            }
        }
    };
    for(int i = 1; i <= m; i++) {
        if(G[i].empty()) {
            go(i, i);
            is[i] = 1;
        } else {
            is[i] = 0;
        }
    }
}
int col[N];
bool bl1[N];
void test() {
    cin >> n >> r >> c;
    prec();
    m = n;
    g.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        pr[i] = p[i] = i;
        is[i] = 1;
    }
    for(int i = 0; i < 500; i++) make(1 + i);
    for(int i = 1; i <= n; i++) {
        if(!is[p[i]]) continue;
        col[p[i]]++;
        if(bl[i]) {
            bl1[p[i]] = 1;
            // cout << i << '\n';
        }
    }
    vector<int> r;
    for(int i = 1; i <= m; i++) {
        if(is[i] && !bl1[i]) {
            r.push_back(col[i]);
        }
    }
    int res = 0;
    sort(r.begin(), r.end());
    for(int i = 0; i < (int)r.size() && r[i] == r[0]; i++) {
        res += r[0];
    }
    cout << r[0] << '\n' << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}   

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 14
Accepted
time: 65ms
memory: 20412kb

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

Test #9:

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

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

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 0
Runtime Error

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%