Submission #678406

#	Time	Username	Problem	Language	Result	Execution time	Memory
678406		jhwest2	Virus Experiment (JOI19_virus)	C++17	100 / 100	906 ms	168772 KiB

virus

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

const int N = 808;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int f(char c) {
    if (c == 'S')
        return 0;
    if (c == 'E')
        return 1;
    if (c == 'N')
        return 2;
    return 3;
}

int vis[N][N];
bool bad[N][N];
vector<pair<int, int>> g[N][N], vec[N][N];
pair<int, int> par[N][N], anc[N][N];

pair<int, int> Find(pair<int, int> a) {
    auto [x, y] = a;
    return par[x][y] = ((par[x][y] == a) ? par[x][y] : Find(par[x][y]));
}
bool ok(int x, int y, pair<int, int> r) {
    if (x <= 0 || y <= 0 || x > n || y > m || a[x][y] == 0)
        return false;
    if (Find({x, y}) == r)
        return false;

    int msk = 0;
    for (int t = 0; t < 4; t++) {
        int nx = x + dx[t];
        int ny = y + dy[t];

        if (nx <= 0 || ny <= 0 || nx > n || ny > m) 
            continue;
        if (Find({nx, ny}) == r)
            msk |= 1 << t;
    }
    return a[x][y] <= limit[msk];
}

void Union(pair<int, int> a, pair<int, int> b) {
    // cout << "UNION " << a.first << ' ' << a.second << ' ' << b.first << ' ' << b.second << '\n';
    a = Find(a); b = Find(b);
    if (a != b) {
        auto [ax, ay] = a;
        auto [bx, by] = b;

        if (vec[ax][ay].size() < vec[bx][by].size()) {
            swap(a, b);
            swap(ax, bx);
            swap(ay, by);
            anc[ax][ay] = anc[bx][by];
        }
            
        par[bx][by] = a;

        for (auto v : vec[bx][by]) {
            vec[ax][ay].push_back(v);
 
            auto [x, y] = v;
            for (int t = 0; t < 4; t++) {
                int nx = x + dx[t];
                int ny = y + dy[t];
 
                if (ok(nx, ny, a))
                    g[ax][ay].push_back({nx, ny});
            }
        }
        
        vector<pair<int, int>>().swap(g[bx][by]);
        vector<pair<int, int>>().swap(vec[bx][by]);
    }
}

bool dfs(int x, int y) {
    // cout << "VISIT " <<  x << ' ' << y << "!\n";

    for (int t = 0; t < 4; t++) {
        int nx = x + dx[t];
        int ny = y + dy[t];

        if (ok(nx, ny, {x, y}))
            g[x][y].push_back({nx, ny});
    }
    
    int s = x, t = y;
    while (!g[s][t].empty()) {
        auto [nx, ny] = g[s][t].back();
        g[s][t].pop_back();

        // cout << x << ' ' << y << ' ' << nx << ' '<< ny << '\n';
        if (!ok(nx, ny, {s, t}))
            continue;
        
        // new vertex
        if (!vis[nx][ny]) {
            vis[nx][ny] = 1;
            anc[nx][ny] = {s, t};
            auto f = dfs(nx, ny);
            // if dfs(nx, ny) visits other scc, not a candidate
            if (!f) {
                bad[s][t] = 1;
                vis[x][y] = 2;
                return false;
            }
        }
        else if (vis[nx][ny] == 1) { // ancestor
            while (Find({nx, ny}) != Find({s, t})) {
                Union(anc[s][t], {s, t});
                tie(s, t) = Find({s, t});
            }
        }
        else { // visits other scc
            bad[s][t] = 1;
            vis[x][y] = 2;
            return false;
        }
        
        tie(s, t) = Find({x, y});
    }
    vis[x][y] = 2;
    return true;
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> k >> n >> m >> s;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    for (int i = 0; i < (1 << 4); i++) {
        int l = -1, r = 0, x = -1;
        for (int j = 0; j < k; j++) {
            if (i >> f(s[j]) & 1)  
                ++r;
            else {
                if (l == -1)
                    l = r;
                x = max(x, r);
                r = 0;
            }
        }
        if (x == -1 && r == 0)
            limit[i] = 0;
        else if (x == -1)
            limit[i] = 1e9 + 10;
        else 
            limit[i] = max(r + l, x);
    }

    // initialize uf
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 0)
                continue;

            par[i][j] = {i, j};
            vec[i][j].push_back({i, j});
        }
    }
    // run dfs
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] && !vis[i][j]) {
                // cout << i << ' ' << j << " START?\n";
                vis[i][j] = 1;
                dfs(i, j);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 0)
                continue;
            if (Find({i, j}) != pair<int, int>{i, j})
                continue;
            
            if (anc[i][j] != pair<int, int>(0, 0)) {
                auto [x, y] = anc[i][j];
                bad[x][y] = 1;
            }
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++) {
    //         auto [x, y] = Find({i, j});

    //         cout << i << ' ' << j << ' ' << x << ' ' << y << '\n';
    //     }
    // }
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 0)
                continue;
            if (Find({i, j}) != pair<int, int>{i, j})
                continue;
            if (!bad[i][j]) 
                mp[vec[i][j].size()] += vec[i][j].size();
        }
    }
    auto [x, y] = *mp.begin();
    cout << x << '\n' << y;
}

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