Submission #1021175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021175		Alihan_8	Virus Experiment (JOI19_virus)	C++17	6 / 100	606 ms	262144 KiB

virus

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

struct Dsu{
    vector <int> fa, pt, isDead;

    int n;

    Dsu(int n_){
        n = n_;

        fa.resize(n);
        pt.resize(n); isDead.resize(n);

        for ( int i = 0; i < n; i++ ){
            fa[i] = pt[i] = i;

            isDead[i] = false;
        }
    }

    int get(int u){
        return fa[u] ^ u ? fa[u] = get(fa[u]) : u;
    }

    bool merge(int u, int v){ // u to v
//        cout << u << " " << v << ln;

        u = get(u), v = get(v);

        if ( u == v ){
            return false;
        }

        fa[u] = v;

        return true;
    }

    void setDead(int u){
        u = get(u);

        isDead[u] = true;
    }

    bool is(int u){ return isDead[get(u)]; }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, r, c; cin >> m >> r >> c;

    string d; cin >> d;

    d += d; m *= 2;

    map <char,int> dir = {{'W', 0}, {'N', 1}, {'E', 2}, {'S', 3}};

    vector <vector<int>> a(r, vector <int> (c));

    vector <vector<vector<int>>> way(r, vector <vector<int>> (c));

    vector <set<pair<int,int>>> st(16);

    for ( int i = 0; i < r; i++ ){
        for ( int j = 0; j < c; j++ ){
            cin >> a[i][j];

            chmin(a[i][j], m);

            for ( int k = 0; k < 16; k++ ){
                st[k].insert({a[i][j], i * c + j});
            }
        }
    }
    if ( r > 50 || c > 50 ){ return cout << "-1\n", 0; }
    { // initializing "way"
        vector <int> nxt(4, m);

        for ( int i = m - 1; i >= 0; i-- ){
            nxt[dir[d[i]]] = i;

            vector <ar<int,2>> p_;

            for ( int j = 0; j < 4; j++ ){
                p_.pb({nxt[j], j});
            }

            sort(all(p_));

            p_.pb({m + 1, 5});

            int mask = 0;

            for ( int k = 0; k < 4; k++ ){
                auto [x, j] = p_[k];

                mask |= 1 << j;

                auto &s = st[mask];

                int r = p_[k + 1][0] - i + 1;

                auto it = s.lower_bound({x - i + 1, -1});

                vector <pair<int,int>> er;

                while ( it != s.end() && it -> first < r ){
                    int y = it -> second;

                    way[y / c][y % c].pb(mask);

                    er.pb(*it);

                    it = next(it);
                }

                for ( auto &y: er ){
                    s.erase(y);
                }
            }
        }

        st.clear();
    }

    auto ok = [&](int x, int y){
        return x >= 0 && y >= 0 && x < r && y < c && (a[x][y] != 0);
    };

    Dsu ds(r * c);

    vector <vector<int>> us(r, vector <int> (c));

    vector <ar<int,2>> tmp;

    auto clear = [&](){
        for ( auto &[x, y]: tmp ){
            us[x][y] = false;
        }

        tmp.clear();
    };

    auto bfs = [&](int su, int sv){
        us[su][sv] = 1;

        int B = ds.get(su * c + sv);

        queue <ar<int,2>> q;

        q.push({su, sv});

        ar <int,2> ret = {0, 0};

        bool has = false;

        while ( !q.empty() ){
            auto [u, v] = q.front();
            q.pop();

            tmp.pb({u, v});

            for ( int i = 0; i < 4; i++ ){
                int x = dx[i] + u, y = dy[i] + v;

                if ( !ok(x, y) || us[x][y] ){
                    continue;
                }

                bool flag = false;

                for ( auto &mask: way[x][y] ){
                    bool ok_ = true;

                    for ( int j = 0; j < 4; j++ ){
                        if ( !(mask >> j & 1) ) continue;

                        int tx = x + dx[j], ty = y + dy[j];

                        if ( !ok(tx, ty) || !us[tx][ty] ){
                            ok_ = false;
                        }
                    }

                    flag |= ok_;
                }

                if ( flag > 0 ){
                    if ( ds.get(x * c + y) != B ){ // new component
                        if ( ds.is(x * c + y) ){
                            has = true;

                            ret = {-1, ds.get(x * c + y)};
                        } else if ( !has ){
                            ret = {-1, ds.get(x * c + y)};
                        }

                        continue;
                    }

                    us[x][y] = true;

                    q.push({x, y});
                }
            }
        }

        if ( ret[0] != -1 ) ret = {tmp.size(), -1};

        return ret;
    };

    int mn = r * c + 1, freq = 0;

    for ( int _ = 1; _ <= 30; _++ ){
        vector <ar<int,2>> pp(r * c);

        for ( int i = 0; i < r * c; i++ ){
            if ( !a[i / c][i % c] ) continue;

            if ( ds.get(i) == i && !ds.is(i) ){
                pp[i] = bfs(ds.pt[i] / c, ds.pt[i] % c);

                clear();
            }
        }

        for ( int i = 0; i < r * c; i++ ){
            if ( !a[i / c][i % c] ) continue;

            if ( ds.get(i) == i && !ds.is(i) ){
                auto p = pp[i];

                if ( p[0] == -1 ){
                    if ( ds.is(p[1]) ){
                        ds.setDead(i);
                    } else{
                        ds.merge(i, p[1]);
                    }
                } else{
                    if ( chmin(mn, p[0]) ){
                        freq = 1;
                    } else if ( mn == p[0] ){
                        freq += 1;
                    }

                    ds.setDead(i);
                }

                clear();
            }
        }
    }

    cout << mn << "\n" << freq * mn << ln;

    cout << '\n';
}

Compilation message (stderr)

virus.cpp: In lambda function:
virus.cpp:241:44: warning: narrowing conversion of '(& tmp)->std::vector<std::array<int, 2> >::size()' from 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  241 |         if ( ret[0] != -1 ) ret = {tmp.size(), -1};
      |                                    ~~~~~~~~^~

• Subtask 1: 0 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80