Submission #1295543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295543		baotoan655	Virus Experiment (JOI19_virus)	C++20	100 / 100	150 ms	21348 KiB

virus

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 805, inf = 1e9;

int ans[N][N];
int sz[N * N], fa[N * N];
int A[N][N], vis[N][N];
string str;
int L, n, m, id_bfs = 0;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
string dir = "NSWE";
int best[20];

void maxi(int &x, int y) {
    if(x < y) x = y;
}
int con(int x, int y) {
    return (x - 1) * m + y;
}
int root(int x) {
    if(x == fa[x]) return x;
    return fa[x] = root(fa[x]);
}
void prep() {
    str = str + str;
    for(auto &c : str) c = find(dir.begin(), dir.end(), c) - dir.begin();
    for(int i = 0; i < (1 << 4); ++i) {
        int  nr = 0;

        for(int j = 0; j < (int)str.size(); ++j) {
            if(i & (1 << str[j])) ++nr;
            else maxi(best[i], nr), nr = 0;
        }
        for(int j = 0; j < (int)str.size(); ++j) {
            if(i & (1 << str[j])) ++nr;
            else break;
        }
        maxi(best[i], nr);

        if(best[i] > (int)str.size() / 2) best[i] = inf;
    }
}

void init() {
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) if(A[i][j]) {
            ans[i][j] = inf;
            int nw = con(i, j);
            fa[nw] = nw;
            sz[nw] = 1;
        }
    }
}

void join(int a, int b) {
    if(sz[b] == -1) {
        sz[a] = -1;
        return;
    }
    fa[a] = b;
    sz[b] += sz[a];
    return;
}

bool bfs(int x, int y) {
    ++id_bfs;

    queue<int> q;
    vector<pair<int, int>> visited;

    visited.emplace_back(x, y);
    vis[x][y] = id_bfs;

    int id = con(x, y);
    int j = 0;

    while(j < (int)visited.size()) {
        tie(x, y) = visited[j++];

        for(int i = 0; i < 4; ++i) {
            int nx, ny;
            nx = x + dx[i];
            ny = y + dy[i];
            if(A[nx][ny] == 0) continue;
            int mask = 0;
            for(int j = 0; j < 4; ++j) if(vis[nx + dx[j]][ny + dy[j]] == id_bfs) mask |= (1 << j);

            if(A[nx][ny] > best[mask]) continue;

            int nid = root(con(nx, ny));

            if(nid == id) {
                if(id_bfs == vis[nx][ny]) continue;
                visited.push_back({nx, ny});
                vis[nx][ny] = id_bfs;
            } else {
                join(id, nid);
                return true;
            }
        }
    }
    sz[id] = -1;
    for(auto it : visited) ans[it.first][it.second] = visited.size();
    return false;
}

bool solve() {
    bool done = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(A[i][j] == 0) continue;
            int curr = con(i, j);
            if(root(curr) == curr && sz[curr] != -1) done |= bfs(i, j);
        }
    }
    return done;
}

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

//    file("A") else file("task");
    cin >> L >> n >> m;
    cin >> str;

    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) cin >> A[i][j];

    prep();
    init();
    bool ok = 1;
    while(ok) ok = solve();
    int mn = inf, cnt = 0;
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)
            if(A[i][j]) {
                if(mn > ans[i][j]) mn = ans[i][j], cnt = 1;
                else if(mn == ans[i][j]) ++cnt;
            }

    cout << mn << '\n' << cnt << '\n';
    return 0;
}

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