Submission #1306524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306524		pvpro	Viruses (BOI20_viruses)	C++20	0 / 100	1 ms	576 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;
        }
    }
    assert(m == 0);
    vector<int> dp(g, (1ll<<63));
    dp[0] = 1;
    dp[1] = 1;
    bool run = true;
    while (run) {
        run = false;
        for (int num = 2; num < g; ++num) {
            for (auto &v : a[num]) {
                int now = 0;
                for (auto &x : v) {
                    now += dp[x];
                }
                if (dp[num] > now) {
                    dp[num] = now;
                    run = true;
                }
            }
        }
    }
    for (int num = 2; num < g; ++num) {
        int ans = dp[num];
        if (ans == (1ll<<63)) {
            cout << "YES" << endl;
        } else {
            cout << "NO " << dp[num] << 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