Submission #491343

#	Time	Username	Problem	Language	Result	Execution time	Memory
491343		doowey	Virus Experiment (JOI19_virus)	C++14	100 / 100	707 ms	25652 KiB

virus

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 805;
int mx[16];
char dir[4] = {'S','N','E','W'};
int di[4][2] = {{-1,0},{+1,0},{0,-1},{0,+1}};
int U[N][N];

void shuffle(vector<pii> &ord){
    int sz = ord.size();
    int ii, jj;
    for(int pi = 0; pi < 4 * sz; pi ++ ){
        ii = ((int)rng() % sz + sz) % sz;
        jj = ((int)rng() % sz + sz) % sz;
        swap(ord[ii], ord[jj]);
    }
}

bool mark[N][N];
bool vis[N][N];
int bits[N][N];

int low = (int)1e9;
int how = 0;

void bfs(int pi, int qi){
    queue<pii> que;
    que.push(mp(pi, qi));
    mark[pi][qi]=true;
    vis[pi][qi]=true;
    vector<pii> delet;
    delet.push_back(mp(pi,qi));
    int total = 0;
    int ni, nj;
    bool terminate = false;
    while(!que.empty() && !terminate){
        pi = que.front().fi;
        qi = que.front().se;
        total ++ ;

        que.pop();
        for(int d = 0; d < 4; d ++ ){
            ni = pi + di[d][0];
            nj = qi + di[d][1];
            if(vis[ni][nj]) continue;
            delet.push_back(mp(ni, nj));
            bits[ni][nj] |= (1 << d);
            if(mx[bits[ni][nj]] >= U[ni][nj]){
                if(mark[ni][nj]){
                    terminate = true;
                    break;
                }
                vis[ni][nj] = true;
                que.push(mp(ni,nj));
            }
        }
    }
    for(auto x : delet){
        vis[x.fi][x.se] = false;
        bits[x.fi][x.se] = false;
    }
    if(!terminate){
        if(total < low){
            low = total;
            how = 0;
        }
        if(total == low){
            how += low;
        }
    }
}

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, m, l;
    cin >> l >> n >> m;
    string s;
    cin >> s;
    string res = "";
    for(int i = 0 ; i < N; i ++ ){
        for(int j = 0 ; j < N ; j ++ ){
            U[i][j] = (int)1e9;
        }
    }
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            cin >> U[i][j];
            if(U[i][j] == 0)
                U[i][j] = (int)1e9;
        }
    }
    while(res.size() < (int)2e5){
        for(int i = 0 ; i < l; i ++ ){
            res.push_back(s[i]);
        }
    }
    bool match;
    int cnt;
    for(int mask = 0 ; mask < 16 ; mask ++ ){
        cnt = 0;
        for(char x : res){
            match = false;
            for(int j = 0 ; j < 4; j ++ ){
                if(dir[j] == x && (mask & (1 << j))){
                    match = true;
                }
            }
            if(match){
                cnt ++ ;
                mx[mask] = max(mx[mask],cnt);
            }
            else{
                cnt = 0;
            }
        }
    }
    vector<pii> ord;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            if(U[i][j] < (int)1e9){
                ord.push_back(mp(i,j));
            }
        }
    }

    shuffle(ord);

    for(auto x : ord){
        bfs(x.fi, x.se);
    }

    cout << low << "\n" << how << "\n";
    return 0;
}

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