oj.uz

Submission #677893

# Submission time Handle Problem Language Result Execution time Memory
677893 2023-01-04T14:38:55 Z qwerasdfzxcl Virus Experiment (JOI19_virus) C++17
100 / 100
 557 ms 120572 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int INF = 1e9+100;
char s[100100];
int L, n, m, a[808][808], mx[16];
int visited[1001000], dfn[1001000], INV[1001000], up[1001000], sz[1001000], cnt;
vector<int> st;
vector<int> go[1001000];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

bool valid(int x, int y){return x>0 && x<=n && y>0 && y<=m;}
int c_to_i(int x, int y){return (x-1)*m + y;}
pair<int, int> i_to_c(int s){return {(s-1)/m+1, (s-1)%m+1};}

/*bool ok(int x, int y, int c){
    if (!a[x][y]) return 0;
    int msk = 0;
    for (int k=0;k<4;k++){
        int nx = x+dx[k], ny = y+dy[k];
        if (valid(nx, ny) && dfn[c_to_i(nx, ny)] >= c) msk |= 1<<k;
    }

    //if (x==1 && y==1 && c==2) printf(" FUCK %d\n", msk);

    return mx[msk] >= a[x][y];
}*/

int ok(int x, int y){
    if (!a[x][y]) return INF;

    vector<pair<int, int>> tmp;
    for (int k=0;k<4;k++){
        int nx = x+dx[k], ny = y+dy[k];
        int np = c_to_i(nx, ny);
        if (valid(nx, ny) && visited[np]) tmp.emplace_back(dfn[np], k);
    }

    sort(tmp.begin(), tmp.end(), greater<pair<int, int>>());
    int msk = 0;
    for (int i=0;i<(int)tmp.size();i++){
        msk |= 1<<(tmp[i].second);
        if (mx[msk] >= a[x][y]){
            int target = tmp[i].first;

            int idx = upper_bound(st.begin(), st.end(), target) - st.begin() - 1;

            //if (x==1 && y==3) printf("%d %d\n", INV[target], idx);
            return st[idx];
        }
    }

    return INF;
}

void dfs(int s){
    visited[s] = 1;
    sz[s] = 1;
    dfn[s] = ++cnt;
    INV[cnt] = s;
    up[s] = dfn[s];

    st.emplace_back(dfn[s]);

    auto [x, y] = i_to_c(s);

    //printf("start = %d %d\n", x, y);

    for (int k=0;k<4;k++){
        int nx = x + dx[k], ny = y + dy[k];
        int np = c_to_i(nx, ny);
        //if (x==1 && y==4 && nx==1 && ny==3) printf("%d\n", INV[ok(nx, ny)]);

        if (!valid(nx, ny)) continue;
        int ps = ok(nx, ny);
        if (ps == INF) continue;

        go[INV[ps]].push_back(np);
    }

    while(!go[s].empty()){
        int v = go[s].back(); go[s].pop_back();
        if (visited[v]) up[s] = min(up[s], dfn[v]);
        else{
            dfs(v);
            sz[s] += sz[v];
            up[s] = min(up[s], up[v]);
        }
    }

    /*vector<int> mychk(4, 0);
    while(true){
        int cnt = 0;

        for (int k=0;k<4;k++) if (!mychk[k]){
            int nx = x + dx[k], ny = y + dy[k];
            int np = c_to_i(nx, ny);
            if (!valid(nx, ny)) continue;
            if (visited[np]){
                if (dfn[np] > dfn[s]) continue;

                if (ok(nx, ny, dfn[s])) {
                    mychk[k] = 1; cnt++;
                    up[s] = min(up[s], dfn[np]);
                    continue;
                }
            }

            if (ok(nx, ny, dfn[s])){
                mychk[k] = 1; cnt++;
                dfs(np);
                sz[s] += sz[np];
                up[s] = min(up[s], up[np]);
            }
        }

        if (cnt==0) break;
    }*/

    auto [ux, uy] = i_to_c(INV[up[s]]);
    //printf("end = %d %d (up = %d %d)\n", x, y, ux, uy);
    st.pop_back();
}

int mp(char x){
    if (x=='N') return 0;
    if (x=='E') return 1;
    if (x=='S') return 2;
    if (x=='W') return 3;
    return -1;
}

void init(int msk){
    vector<pair<int, int>> ran;
    for (int i=1;i<=L;i++){
        int typ = mp(s[i]);
        if (!(msk & (1<<typ))) continue;

        if (ran.empty() || ran.back().second+1 < i) ran.emplace_back(i, i);
        else ran.back().second++;
    }

    if (ran.empty()) mx[msk] = 0;
    else if (ran[0]==make_pair(1, L)) mx[msk] = 1e9;
    else{
        for (auto &[l, r]:ran) mx[msk] = max(mx[msk], r-l+1);
        if (ran.back().second==L && ran[0].first==1){
            mx[msk] = max(mx[msk], ran[0].second+L - ran.back().first + 1);
        }
    }

    //printf(" msk = %d -> %d\n", msk, mx[msk]);
}

int main(){
    scanf("%d %d %d", &L, &n, &m);
    scanf("%s", s+1);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
    }

    for (int i=0;i<16;i++) init(i);

    st.push_back(0);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            int p = c_to_i(i, j);
            if (visited[p] || a[i][j]==0) continue;
            dfs(p);
        }
    }

    int ans = 1e9, cnt = 0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) if (a[i][j]){
            int p = c_to_i(i, j);
            if (up[p] == dfn[p]){
                if (ans==sz[p]) cnt += sz[p];
                else if (ans > sz[p]) ans = sz[p], cnt = sz[p];

            }
        }
    }

    printf("%d\n%d\n", ans, cnt);
    return 0;
}

Compilation message

virus.cpp: In function 'void dfs(int)':
virus.cpp:121:10: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  121 |     auto [ux, uy] = i_to_c(INV[up[s]]);
      |          ^~~~~~~~
virus.cpp: In function 'int main()':
virus.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |     scanf("%d %d %d", &L, &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |     scanf("%s", s+1);
      |     ~~~~~^~~~~~~~~~~
virus.cpp:160:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
      |                                ~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 347 ms 55672 KB Output is correct
3 Correct 350 ms 63716 KB Output is correct
4 Correct 322 ms 62640 KB Output is correct
5 Correct 327 ms 47212 KB Output is correct
6 Correct 14 ms 26324 KB Output is correct
7 Correct 372 ms 63108 KB Output is correct
8 Correct 136 ms 33236 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 16 ms 23920 KB Output is correct
3 Correct 31 ms 24436 KB Output is correct
4 Correct 17 ms 23892 KB Output is correct
5 Correct 30 ms 24380 KB Output is correct
6 Correct 32 ms 24540 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 29 ms 24536 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 18 ms 23996 KB Output is correct
11 Correct 14 ms 24120 KB Output is correct
12 Correct 14 ms 24148 KB Output is correct
13 Correct 33 ms 24504 KB Output is correct
14 Correct 31 ms 24512 KB Output is correct
15 Correct 30 ms 24524 KB Output is correct
16 Correct 29 ms 24504 KB Output is correct
17 Correct 22 ms 24228 KB Output is correct
18 Correct 14 ms 24092 KB Output is correct
19 Correct 30 ms 24504 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 347 ms 55672 KB Output is correct
3 Correct 350 ms 63716 KB Output is correct
4 Correct 322 ms 62640 KB Output is correct
5 Correct 327 ms 47212 KB Output is correct
6 Correct 14 ms 26324 KB Output is correct
7 Correct 372 ms 63108 KB Output is correct
8 Correct 136 ms 33236 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 16 ms 23920 KB Output is correct
11 Correct 31 ms 24436 KB Output is correct
12 Correct 17 ms 23892 KB Output is correct
13 Correct 30 ms 24380 KB Output is correct
14 Correct 32 ms 24540 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 29 ms 24536 KB Output is correct
17 Correct 14 ms 24020 KB Output is correct
18 Correct 18 ms 23996 KB Output is correct
19 Correct 14 ms 24120 KB Output is correct
20 Correct 14 ms 24148 KB Output is correct
21 Correct 33 ms 24504 KB Output is correct
22 Correct 31 ms 24512 KB Output is correct
23 Correct 30 ms 24524 KB Output is correct
24 Correct 29 ms 24504 KB Output is correct
25 Correct 22 ms 24228 KB Output is correct
26 Correct 14 ms 24092 KB Output is correct
27 Correct 30 ms 24504 KB Output is correct
28 Correct 533 ms 108020 KB Output is correct
29 Correct 557 ms 104316 KB Output is correct
30 Correct 452 ms 61000 KB Output is correct
31 Correct 485 ms 59716 KB Output is correct
32 Correct 466 ms 60008 KB Output is correct
33 Correct 348 ms 57760 KB Output is correct
34 Correct 485 ms 72860 KB Output is correct
35 Correct 394 ms 84788 KB Output is correct
36 Correct 470 ms 60912 KB Output is correct
37 Correct 508 ms 77892 KB Output is correct
38 Correct 510 ms 120572 KB Output is correct
39 Correct 430 ms 61864 KB Output is correct
40 Correct 458 ms 62080 KB Output is correct
41 Correct 307 ms 56668 KB Output is correct
42 Correct 363 ms 78008 KB Output is correct
43 Correct 492 ms 61096 KB Output is correct
44 Correct 141 ms 32456 KB Output is correct