Submission #678408

#	Time	Username	Problem	Language	Result	Execution time	Memory
678408		jhwest2	Virus Experiment (JOI19_virus)	C++17	0 / 100	275 ms	72960 KiB

virus

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int N = 707070;
const int INF = 1e9 + 10;

int n, m, len, a[N], limit[1 << 4]; string s;

int encode(char c) {
    if (c == 'S')
        return 0;
    else if (c == 'E')
        return 1;
    else if (c == 'N')
        return 2;
    else
        return 3;
}
int f(int x, int y) { 
    return m * (x - 1) + (y - 1) + 1;
}
pair<int, int> g(int x) {
    return { (x - 1) / m + 1, (x - 1) % m + 1 };
}
bool in(int x, int y) {
    return (1 <= x && x <= n && 1 <= y && y <= m);
}

int par[N], anc[N], vis[N];
vector<int> cell[N], adj[N];
bool bad[N];

int Find(int a) {
    return par[a] = (par[a] == a) ? a : Find(par[a]);
}
bool ok(int v, int r) { // check if cell v is reachable from component r
    auto [x, y] = g(v);
    if (!in(x, y) || a[v] == 0 || Find(v) == r)
        return false;
    
    int msk = 0;
    for (int t = 0; t < 4; t++) {
        int nx = x + dx[t];
        int ny = y + dy[t];
        int w = f(nx, ny);

        if (in(nx, ny) && a[w] && Find(w) == r)
            msk |= 1 << t;
    }
    return a[v] <= limit[msk];
}
void Union(int a, int b) {
    a = Find(a); b = Find(b);
    if (a != b) {
        if (cell[a].size() < cell[b].size()) {
            swap(a, b);
            anc[a] = anc[b];
        }
        par[b] = a;

        for (int v : cell[b]) {
            cell[a].push_back(v);

            auto [x, y] = g(v);
            for (int t = 0; t < 4; t++) {
                int nx = x + dx[t];
                int ny = y + dy[t];
                int w = f(nx, ny);

                if (ok(w, a))
                    adj[a].push_back(w);
            }
        }
        vector<int>().swap(cell[b]);
        vector<int>().swap(adj[b]);
    }
}
bool dfs(int v) {
    auto [x, y] = g(v); 
    for (int t = 0; t < 4; t++) {
        int nx = x + dx[t];
        int ny = y + dy[t];
        int w = f(nx, ny);

        if (ok(w, v))
            adj[v].push_back(w);
    }
    int s = Find(v);
    while (!adj[s].empty()) {
        int z = adj[s].back(); 
        adj[s].pop_back();

        if (!ok(z, s))
            continue;

        if (vis[z] == 0) {
            vis[z] = 1;
            anc[z] = v;
            bool f = dfs(z);

            if (!f) {
                vis[v] = 2;
                bad[s] = 1;
                return false;
            }
        }
        else if (vis[z] == 1) {
            while (Find(s) != Find(z)) {
                Union(anc[s], s);
                s = Find(s);
            }
        }
        else {
            vis[v] = 2;
            bad[s] = 1;
            return false;
        }
        s = Find(v);
    }
    vis[v] = 2;
    return true;
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> len >> n >> m >> s;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) 
            cin >> a[f(i, j)];
    
    // upper bound for each direction set
    for (int msk = 0; msk < (1 << 4); msk++) {
        vector<int> v;
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            if (msk >> encode(s[i]) & 1)
                ++cnt;
            else {
                if (cnt)
                    v.push_back(cnt);
                cnt = 0;
            }
        }
        if (cnt)
            v.push_back(cnt);

        if (v.empty())
            limit[msk] = 0;
        else if (v[0] == len)
            limit[msk] = INF;
        else {
            if (v.size() == 1)
                limit[msk] = v[0];
            else
                limit[msk] = max(v[0] + v.back(), *max_element(v.begin(), v.end()));
        }
    }
    
    for (int i = 1; i <= n * m; i++) {
        par[i] = i;
        cell[i].push_back(i);
    }
    for (int i = 1; i <= n * m; i++) {
        if (a[i] && !vis[i]) {
            vis[i] = 1;
            dfs(i);
        }
    }

    for (int i = 1; i <= n * m; i++) 
        if (a[i] && Find(i) == i)
            bad[anc[i]] = 1;

    map<int, int> mp;
    for (int i = 1; i <= n * m; i++) 
        if (a[i] && Find(i) == i && !bad[i])
            mp[cell[i].size()] += cell[i].size();
    
    cout << mp.begin()->first << '\n';
    cout << mp.begin()->second << '\n';
}

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