Submission #1306518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306518		pvpro	Viruses (BOI20_viruses)	C++20	0 / 100	25 ms	1632 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 = 1010;
int nextt[MAXV][K], go1[MAXV][K];
int suflink[MAXV], par[MAXV], lch[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]);
}
}
}
}

void solve() {
    int g, n, m;
    cin >> g >> n >> m;
    vector<vector<vector<int>>> a(g);
    for (int i = 0; i < n; ++i) {
        int f, sz;
        cin >> f >> sz;
        a[f].pb(vector<int>(sz));
        for (auto &x : a[f].back()) {
            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);
    vector<vector<vector<int>>> dp(g, vector<vector<int>>(S, vector<int>(S, (1ll<<63))));
    for (int i = 0; i < S; ++i) {
        if (last1[i].empty()) {
            if (last1[go1[i][0]].empty()) {
                dp[0][i][go1[i][0]] = 1;
            }
            if (last1[go1[i][1]].empty()) {
                dp[1][i][go1[i][1]] = 1;
            }
        }
    }
    bool run = true;
    while (run) {
        run = false;
        for (int num = 2; num < g; ++num) {
            for (int f = 0; f < S; ++f) {
                if (last1[f].empty()) {
                    for (auto &v : a[num]) {
                        vector<int> now(S, (1ll<<63));
                        now[f] = 0;
                        for (auto &x : v) {
                            vector<int> now2(S, (1ll<<63));
                            for (int tnow = 0; tnow < S; ++tnow) {
                                if (last1[tnow].empty()) {
                                    for (int fnow = 0; fnow < S; ++fnow) {
                                        now2[tnow] = min(now2[tnow], now[fnow] + dp[x][fnow][tnow]);
                                    }
                                }
                            }
                            now = now2;
                        }
                        for (int t = 0; t < S; ++t) {
                            if (dp[num][f][t] > now[t]) {
                                run = true;
                                dp[num][f][t] = now[t];
                            }
                        }
                    }
                }
            }
        }
    }
    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: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18