Submission #1110902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110902		Zero_OP	Viruses (BOI20_viruses)	C++14	0 / 100	24 ms	2640 KiB

Viruses

#include <bits/stdc++.h>

#define sz(v) (int)v.size()

using namespace std;
using ull = unsigned long long;

const ull inf = (1ULL << 63);

ull add(ull a, ull b){
    return (a == inf || b == inf || a > inf - b ? inf : a + b);
}

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        } return false;
    }

template<int dimension, typename T>
struct tensor : public vector<tensor<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {}
};

template<typename T>
struct tensor<1, T> : public vector<T> {
    tensor(int n = 0, T val = T()) : vector<T>(n, val) {}
};

int G, N, M;
vector<int> mutations[150], adj[150];

int nxt[51][2], fail[51], bad[51], aho_size;

void initAho(){
    memset(nxt, -1, sizeof(nxt));
    memset(fail, -1, sizeof(fail));
    aho_size = 1;
}

void addString(const vector<int>& s){
    int u = 0;
    for(int c : s){
        if(nxt[u][c] == -1){
            nxt[u][c] = aho_size++;
        }

        u = nxt[u][c];
    }
    bad[u] |= 1;
}

void compute_links(){
    queue<int> q; q.push(0);
    while(!q.empty()){
        int u = q.front(), fail = ::fail[u]; q.pop();
        if(u > 0) bad[u] |= bad[fail];
        for(int c = 0; c < 2; ++c){
            int& aut = nxt[u][c], aut_link = (u ? nxt[fail][c] : 0);
            if(aut == -1) aut = aut_link;
            else{
                ::fail[aut] = aut_link;
                q.push(aut);
            }
        }
    }
}

int oldG;
void preprocess(){ //a -> <x, y>
    oldG = G;
    for(int a = 2; a < oldG; ++a){
        for(int id : adj[a]){
            while((int)mutations[id].size() > 2){
                int u = mutations[id][sz(mutations[id]) - 2];
                int v = mutations[id][sz(mutations[id]) - 1];
                mutations[id].pop_back(); mutations[id].pop_back();
                adj[G].emplace_back(N);
                mutations[N].emplace_back(u);
                mutations[N].emplace_back(v);
                mutations[id].emplace_back(N);
                ++G; ++N;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> G >> N >> M;
    for(int i = 0; i < N; ++i){
        int a, k;
        cin >> a >> k;
        vector<int> b(k);
        for(int j = 0; j < k; ++j) cin >> b[j];
        mutations[i] = b;
        adj[a].emplace_back(i);
    }

    initAho();

    for(int i = 0; i < M; ++i){
        int k;
        cin >> k;
        vector<int> s(k);
        for(int j = 0; j < k; ++j) cin >> s[j];
        addString(s);
    }

    compute_links();
    preprocess();

    tensor<3, ull> dp(G, aho_size, aho_size, inf);

    for(int a = 0; a < G; ++a){
        for(int u = 0; u < aho_size; ++u) if(!bad[u]){
            for(int id : adj[a]){
                bool ok = true;
                int v = u;

                for(auto it : mutations[id]){
                    if(it > 1){
                        ok = false;
                        break;
                    }

                    v = nxt[v][it];
                    if(bad[u]){
                        ok = false;
                        break;
                    }
                }

                if(ok) {
                    ull cur = sz(mutations[id]);
                    minimize(dp[a][u][v], cur);
                }
            }
        }
    }

    for(int a = 0; a < 2; ++a){
        for(int u = 0; u < aho_size; ++u) if(!bad[u]){
            int cur = nxt[u][a];
            if(cur == -1 || bad[u]) continue;
            minimize(dp[a][u][cur], 1ULL);
        }
    }

    while(true){
        bool can_minimize = false;
        for(int a = 0; a < G; ++a){
            for(int id : adj[a]){
                assert(sz(mutations[id]) < 3);

                if(sz(mutations[id]) == 1){
                    int b = mutations[id][0];
                    for(int u = 0; u < aho_size; ++u) if(!bad[u]){
                        for(int v = 0; v < aho_size; ++v) if(!bad[v]){
                            if(minimize(dp[a][u][v], dp[b][u][v])) can_minimize = true;
                        }
                    }
                } else{
                    int b1 = mutations[id][0], b2 = mutations[id][1];
                    for(int u = 0; u < aho_size; ++u) if(!bad[u]){
                        for(int v = 0; v < aho_size; ++v) if(!bad[v]){
                            for(int x = 0; x < aho_size; ++x) if(!bad[x]){
                                if(minimize(dp[a][u][v], add(dp[b1][u][x], dp[b2][x][v]))) can_minimize = true;
                            }
                        }
                    }
                }
            }
        }

        if(!can_minimize) break;
    }

//    cout << aho_size << '\n';
//    for(int a = 0; a < G; ++a){
//    {
//        int a = 3;
//        for(int u = 0; u < aho_size; ++u){
//            for(int v = 0; v < aho_size; ++v){
//                cout << "(" << a << ", " << u << ", " << v << ") = " << dp[a][u][v] << '\n';
//            }
//        }
//    }

    for(int a = 2; a < oldG; ++a){
        ull res = inf;
        for(int v = 0; v < aho_size; ++v){
            minimize(res, dp[a][0][v]);
        }

        if(res == inf) cout << "YES\n";
        else cout << "NO " << res << '\n';
    }



    return 0;
}

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