Submission #489466

#	Time	Username	Problem	Language	Result	Execution time	Memory
489466		wiwiho	Virus Experiment (JOI19_virus)	C++14	6 / 100	2072 ms	6728 KiB

virus

#include<bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n";\
}
#define eb emplace_back

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int m, r, c;
string wst;
vector<int> wind;
vector<vector<int>> g;
map<char, int> dirid;
vector<pii> dir = {mp(0, 1), mp(0, -1), mp(1, 0), mp(-1, 0)};
vector<int> len;

vector<vector<int>> status;
vector<vector<bool>> vst;

void init(){
    g.resize(r + 2, vector<int>(c + 2));
    wind.resize(m);
    len.resize(16);
    dirid['W'] = 0;
    dirid['E'] = 1;
    dirid['N'] = 2;
    dirid['S'] = 3;
}

int check(int sx, int sy){
    status.clear();
    vst.clear();
    status.resize(r + 2, vector<int>(c + 2));
    vst.resize(r + 2, vector<bool>(c + 2));

    queue<pii> q;
    q.push(mp(sx, sy));
    int ans = 0;
    vst[sx][sy] = true;

    //cerr << "check " << sx << " " << sy << "\n";
    while(!q.empty()){
        int x = q.front().F, y = q.front().S;
        q.pop();
        ans++;
        //cerr << "test " << x << " " << y << "\n";

        for(int d = 0; d < 4; d++){
            int nx = x + dir[d].F, ny = y + dir[d].S;
            if(!g[nx][ny] || vst[nx][ny]) continue;
            status[nx][ny] |= 1 << d;
            if(len[status[nx][ny]] < g[nx][ny]) continue;
            vst[nx][ny] = true;
            q.push(mp(nx, ny));
        }
    }

    //cerr << "ok " << ans << "\n";
    return ans;
}

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

    cin >> m >> r >> c;
    cin >> wst;
    init();

    for(int i = 0; i < m; i++) wind[i] = dirid[wst[i]];

    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++) cin >> g[i][j];
    }

    for(int i = 0; i < (1 << 4); i++){
        int now = 0;
        for(int j = 0; j < 3e5; j++){
            if(1 << wind[j % m] & i) now++;
            else now = 0;
            len[i] = max(len[i], now);
        }
        //cerr << "len " << bitset<4>(i) << " " << len[i] << "\n";
    }

    int ans = INT_MAX;
    int cnt = 0;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            if(g[i][j] == 0) continue;
            int tans = check(i, j);
            if(tans < ans){
                ans = tans;
                cnt = 1;
            }
            else if(tans == ans) cnt++;
        }
    }

    cout << ans << "\n" << cnt << "\n";

    return 0;
}

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