제출 #1306555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306555		pvpro	Viruses (BOI20_viruses)	C++20	50 / 100	277 ms	7060 KiB

Viruses

#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned ll;

#define int ull

#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()
#ifndef LOCAL
#define endl "\n"
#endif

mt19937 rnd(11);

const int K = 2;
const int MAXV = 110;
int nextt[MAXV][K], go1[MAXV][K];
int suflink[MAXV], par[MAXV], lch[MAXV], bad[MAXV];
vector<int> last1[MAXV];
int S = 1;
void add_word(string s, int ind) {
int cur = 0;
for (int i = 0; i < (int) s.size(); i++) {
if (nextt[cur][s[i] - '0'] == -1) {
int nw = S;
par[nw] = cur;
lch[nw] = s[i] - '0';
for (int j = 0; j < K; j++) {
nextt[nw][j] = -1;
go1[nw][j] = -1;
}
suflink[nw] = -1;;
S++;
nextt[cur][s[i] - '0'] = nw;
}
cur = nextt[cur][s[i] - '0'];
}
last1[cur].push_back(ind);
}
int go(int v, int c);
int link(int v) {
if (suflink[v] == -1) {
if (v == 0 || par[v] == 0) {
suflink[v] = 0;
} else {
suflink[v] = go(link(par[v]), lch[v]);
}
}
return suflink[v];
}
int go(int v, int c) {
if (go1[v][c] == -1) {
if (nextt[v][c] != -1) {
go1[v][c] = nextt[v][c];
} else if (v == 0) {
go1[v][c] = 0;
} else {
go1[v][c] = go(link(v), c);
}
}
return go1[v][c];
}
void build(vector<string> s) {
for (int i = 0; i < K; i++) {
nextt[0][i] = -1;
go1[0][i] = -1;
}
suflink[0] = -1;
par[0] = -1;
lch[0] = -1;
for (int i = 0; i < (int) s.size(); i++)
add_word(s[i], i);
stack<int> st;
st.push(0);
while (!st.empty()) {
int cur = st.top();
st.pop();
link(cur);
for (int i = 0; i < K; i++) {
go(cur, i);
if (nextt[cur][i] != -1) {
st.push(nextt[cur][i]);
}
}
}
}

bool checkEmp(int v) {
    while (v) {
        if (!last1[v].empty()) {
            return false;
        }
        v = suflink[v];
    }
    return true;
}

void solve() {
    int g, n, m;
    cin >> g >> n >> m;
    vector<pair<int, vector<int>>> a(n);
    for (int i = 0; i < n; ++i) {
        int f, sz;
        cin >> f >> sz;
        a[i] = mp(f, vector<int>(sz));
        for (auto &x : a[i].s) {
            cin >> x;
        }
    }
    vector<string> s(m);
    for (auto &x : s) {
        int sz;
        cin >> sz;
        for (int i = 0; i < sz; ++i) {
            char c;
            cin >> c;
            x += c;
        }
    }
    build(s);
    for (int i = 0; i < S; ++i) {
        bad[i] = checkEmp(i);
    }
    queue<int> q;
    vector<int> marked(a.size(), 1e9);
    vector<vector<vector<int>>> dp(g, vector<vector<int>>(S, vector<int>(S, (1ll<<63))));
    auto upd = [&](int i) {
        for (int j = 0; j < a.size(); ++j) {
            int pos = -1;
            for (auto &x : a[j].s) {
                ++pos;
                if (x == i) {
                    if (marked[j] == 1e9) {
                        q.push(j);                        
                    }
                    marked[j] = min(marked[j], pos);
                    break;
                }
            }
        }
    };
    for (int i = 0; i < S; ++i) {
        if (bad[i]) {
            if (bad[go1[i][0]]) {
                dp[0][i][go1[i][0]] = 1;
            }
            if (bad[go1[i][1]]) {
                dp[1][i][go1[i][1]] = 1;
            }
        }
    }
    upd(0);
    upd(1);
    vector<vector<vector<vector<int>>>> now(a.size(), vector<vector<vector<int>>>(S));
    for (int i = 0; i < a.size(); ++i) {
        for (int f = 0; f < S; ++f) {
            now[i][f].resize(a[i].s.size() + 1);
            now[i][f][0].assign(S, (1ll<<63));
            now[i][f][0][f] = 0;
            for (int j = 1; j <= a[i].s.size(); ++j) {
                now[i][f][j].assign(S, (1ll<<63));
            }
        }
    }
    while (!q.empty()) {
        int num = q.front();
        q.pop();
        for (int f = 0; f < S; ++f) {
            for (int i = marked[num]; i < a[num].s.size(); ++i) {
                for (int fnow = 0; fnow < S; ++fnow) {
                    if (now[num][f][i][fnow] < (1ll<<63)) {
                        for (int tnow = 0; tnow < S; ++tnow) {
                            if (bad[tnow]) {
                                now[num][f][i + 1][tnow] = min(now[num][f][i + 1][tnow], now[num][f][i][fnow] + dp[a[num].s[i]][fnow][tnow]);
                            }
                        }
                    }
                }
            }
            for (int t = 0; t < S; ++t) {
                if (dp[a[num].f][f][t] > now[num][f][a[num].s.size()][t]) {
                    dp[a[num].f][f][t] = now[num][f][a[num].s.size()][t];
                    upd(a[num].f);
                }
            }
        }
        marked[num] = 1e9;
    }
    for (int num = 2; num < g; ++num) {
        int ans = (1ll<<63);
        for (int t = 0; t < S; ++t) {
            ans = min(ans, dp[num][0][t]);
        }
        if (ans == (1ll<<63)) {
            cout << "YES" << endl;
        } else {
            cout << "NO " << ans << endl;
        }
    }
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18