Submission #1111052

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

Viruses

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))

struct AhoCorasick{
    vector<int> link, bad;
    vector<array<int, 2>> next;

    int size(){ return (int)link.size(); }
    void extend(){ link.emplace_back(-1); bad.emplace_back(0); next.emplace_back(array<int, 2>{-1, -1}); }

    AhoCorasick() : link(), bad(), next() { extend(); }

    void add(const vector<int>& s){
        int u = 0;
        for(auto c : s){
            if(next[u][c] == -1){
                next[u][c] = size();
                extend();
            }
            u = next[u][c];
        }
        bad[u] = 1;
    }

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

    int go(int u, int c){ return next[u][c]; }
    int check(int u){ return !bad[u]; }
};

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

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

    int G, N, M;
    cin >> G >> N >> M;
    int base = G;
    vector<int> from(N);
    vector<vector<int>> mutations(N);

    for(int i = 0; i < N; ++i){
        int a, k; cin >> a >> k;
        vector<int> mut(k);
        for(int &j : mut) cin >> j;

        while((int)mut.size() > 2){
            int v1 = mut[(int)mut.size() - 2];
            int v2 = mut.back();
            mut.pop_back();
            mut.pop_back();

            mutations.emplace_back();
            mutations.back().emplace_back(v1);
            mutations.back().emplace_back(v2);

            from.emplace_back(G);
            mut.push_back(G);
            ++G;
        }

        from[i] = a;
        mutations[i] = mut;
    }

    AhoCorasick T;
    for(int i = 0; i < M; ++i){
        int l; cin >> l;
        vector<int> s(l);
        for(int& j : s) cin >> j;
        T.add(s);
    }

    T.compute_links();

    int aho_size = T.size();

    using ull = unsigned long long;
    using state = tuple<ull, int, int, int>;
    const ull inf = 1ULL << 63;

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

    vector<vector<vector<ull>>> dist(G, vector<vector<ull>>(aho_size, vector<ull>(aho_size, inf)));
    priority_queue<state, vector<state>, greater<state>> pq;

    for(int c = 0; c < 2; ++c){
        for(int u = 0; u < aho_size; ++u) if(T.check(u)){
            int v = T.go(u, c);
            if(v == -1 || !T.check(v)) continue;
            dist[c][u][v] = 1;
            pq.push({1, c, u, v});
        }
    }

    /*

    single_transform : a -> <x>
    a -> <x, y>

    transition 1 : for a -> <x>
    => dp[a][u][v] = min(dp[a][u][v], dp[x][u][v]

    transition 2 : for a -> <x, y>
    => dp[a][u][v] = min(dp[a][u][v], dp[x][u][pre] + dp[y][pre][v]

    */
    vector<vector<int>> single_transform(G), x_transform(G), y_transform(G);

    N = sz(from);
    for(int i = 0; i < N; ++i){
        assert(sz(mutations[i]) <= 2);

        if(sz(mutations[i]) == 1){
            int x = mutations[i][0];
            single_transform[x].emplace_back(i); // a -> <x>
        } else{
            int x1 = mutations[i][0], x2 = mutations[i][1];
            x_transform[x1].emplace_back(i); // -> a -> <x, ?>
            y_transform[x2].emplace_back(i); // -> a -> <?, y>
        }
    }

    while(!pq.empty()){
        ull cur; int c, u, v;
        tie(cur, c, u, v) = pq.top(); pq.pop();

        if(cur != dist[c][u][v]) continue;

        for(int id : single_transform[c]){
            int a = from[id];
            //dp[a][u][v] = dp[x][u][v]
            if(minimize(dist[a][u][v], cur)){
                pq.push({dist[a][u][v], a, u, v});
            }
        }

        for(int id : x_transform[c]){
            int a = from[id], x = c, y = mutations[id][1];
            //dp[a][u][?] = dp[x][u][v] + dp[y][v][?]
            for(int last = 0; last < aho_size; ++last){
                if(minimize(dist[a][u][last], add(cur, dist[y][v][last]))){
                    pq.push({dist[a][u][last], a, u, last});
                }
            }
        }

        for(int id : y_transform[c]){
            int a = from[id], x = mutations[id][0], y = c;
            //dp[a][?][v] = dp[x][?][u] + dp[y][u][v]
            for(int start = 0; start < aho_size; ++start){
                if(minimize(dist[a][start][v], add(dist[x][start][u], cur))){
                    pq.push({dist[a][start][v], a, start, v});
                }
            }
        }
    }

    for(int i = 2; i < base; ++i){
        ull res = inf;
        for(int u = 0; u < aho_size; ++u){
            minimize(res, dist[i][0][u]);
        }

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

    return 0;
}

Compilation message (stderr)

Viruses.cpp: In function 'int main()':
Viruses.cpp:166:31: warning: unused variable 'x' [-Wunused-variable]
  166 |             int a = from[id], x = c, y = mutations[id][1];
      |                               ^
Viruses.cpp:176:53: warning: unused variable 'y' [-Wunused-variable]
  176 |             int a = from[id], x = mutations[id][0], y = c;
      |                                                     ^

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