Submission #677893

#	Time	Username	Problem	Language	Result	Execution time	Memory
677893		qwerasdfzxcl	Virus Experiment (JOI19_virus)	C++17	100 / 100	557 ms	120572 KiB

virus

#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 (stderr)

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 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80