Submission #1217303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217303		JooDdae	Virus Experiment (JOI19_virus)	C++20	100 / 100	416 ms	149896 KiB

virus

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

#define id(x, y) ((x-1)*m+y-1)
#define coord(id) make_pair(id/m+1, id%m+1)

const string S = "NSWE";
const int dx[4] = {-1, 1, 0 ,0}, dy[4] = {0, 0, -1, 1};

int n, m, k, c[100100], a[808][808], p[700700], mx[16], chk[700700], chk2[808][808][4], out[700700];
vector<int> v[700700], nxt[700700], used[700700];
string s;

int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

int findEdge(int x, int y, int d, int P) {
    if(!a[x][y] || chk2[x][y][d]) return -1;

    int B = 0;
    for(int i=0;i<4;i++) {
        int xx = x+dx[i], yy = y+dy[i];
        if(1 <= xx && xx <= n && 1 <= yy && yy <= m && find(id(xx, yy)) == find(P)) B |= 1 << i;
    }
    if(mx[B] >= a[x][y]) {
        chk2[x][y][d] = 1;
        return id(x, y);
    }
    return -1;
}

void merge(int x, int y) {
    if((x = find(x)) == (y = find(y))) return;
    if(v[x].size() < v[y].size()) swap(v[x], v[y]);
    if(nxt[x].size() < nxt[y].size()) swap(nxt[x], nxt[y]);
    p[y] = x;
    for(auto i : nxt[y]) nxt[x].push_back(i);

    for(auto i : v[y]) {
        v[x].push_back(i);
        auto [X, Y] = coord(i);
        for(int i=0;i<4;i++) {
            auto B = findEdge(X+dx[i], Y+dy[i], i^1, x);
            if(B != -1) nxt[x].push_back(B);
        }
    }
    nxt[y].clear(), v[y].clear();
}

vector<int> st;

void dfs(int u) {
    u = find(u);
    if(chk[u] == 2) return;

    if(chk[u] == 1) {
        for(int i=int(st.size())-1;st[i]!=u;i--) merge(u, find(st[i]));
        return;
    }

    chk[u] = 1;
    st.push_back(u);

    while(!nxt[u].empty()) {
        int x = find(nxt[u].back()); nxt[u].pop_back();
        if(x == find(u)) continue;
        used[u].push_back(x), dfs(x);
    }

    chk[u] = 2;
    st.pop_back();
}

int main() {
    cin.tie(0)->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<n*m;i++) p[i] = i, v[i].push_back(i);
    for(int i=0;i<k;i++) c[i] = 1 << (find(S.begin(), S.end(), s[i]) - S.begin());
    for(int b=1;b<16;b++) {
        for(int i=0;i<k;i++) if(c[i] & b) {
            int j = (i+1)%k, cnt = 1;
            while(j != i && (c[j] & b)) j = (j+1)%k, cnt++;
            mx[b] = max(mx[b], cnt);
            if(j <= i) break;
            i = j;
        }
        if(mx[b] == k) mx[b] = 1e9;
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) for(int d=0;d<4;d++) {
        auto B = findEdge(i+dx[d], j+dy[d], d^1, id(i, j));
        if(B != -1) nxt[id(i, j)].push_back(B);
    }
    for(int i=0;i<n*m;i++) if(!chk[i]) dfs(i);

    int cnt = 1e9, cnt2 = 0;
    for(int i=0;i<n*m;i++) if(i == find(i) && a[i/m+1][i%m+1]) {
        bool flag = 0;
        for(auto u : v[i]) for(auto x : used[u]) if(find(u) != find(x)) flag = 1;
        if(flag) continue;

        if(v[i].size() < cnt) cnt = v[i].size(), cnt2 = 1;
        else if(v[i].size() == cnt) cnt2++;
    }
    cout << cnt << "\n" << cnt * cnt2 << "\n";
}

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