Submission #1185822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185822		steveonalex	Viruses (BOI20_viruses)	C++20	36 / 100	54 ms	7612 KiB

Viruses

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}

ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
// mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }

template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

struct Trie{
    static const int K = 2;
    struct Node{
        int child[K], nxt[K];
        Node(){memset(child, -1, sizeof child); memset(nxt, 0, sizeof nxt);}
    };

    int n;
    vector<Node> a;
    vector<int> pi;

    Trie(){
        a.push_back(Node());
    }

    void add_child(int &x){
        x = a.size();
        a.push_back(Node());
    }

    void add(vector<int> s){
        int id=  0;
        for(int c: s){
            int digit = c;
            if (a[id].child[digit] == -1) add_child(a[id].child[digit]);
            id = a[id].child[digit];
        }
    }

    int locate(vector<int> s){
        int id = 0;
        for(int c: s){
            id = a[id].child[c];
        }
        return id;
    }

    void build_kmp(){
        pi.resize(a.size(), -1);
        deque<int> q; q.push_back(0);
        while(q.size()){
            int u = q.front();
            q.pop_front();

            if (pi[u] >= 0)
                for(int j = 0; j<K; ++j) a[u].nxt[j] = a[pi[u]].nxt[j];

            for(int j = 0; j < K; ++j) if (a[u].child[j] != -1){
                int v = a[u].child[j];
                pi[v] = a[u].nxt[j];
                a[u].nxt[j] = v;
                q.push_back(v);
            }
        }
    }
};

const int N = 101;
const int K = 51;
const ll INF = 1e18 + 69;
ll edge[N][K][K];
ll dp[N * 2][K][K];

struct P{
    int i, j, k;
    ll w;

    P(int i = 0, int j = 0, int k = 0, ll w = 0): i(i), j(j), k(k), w(w){}
};

struct compare{
    bool operator () (P a, P b) {return a.w > b.w;}
};

void solve(){
    int g, n, m; cin >> g >> n >> m;
    vector<vector<int>> mutation(n);
    for(int i = 0; i < n; ++i){
        int a, k; cin >> a >> k;
        mutation[i].resize(k + 1);
        mutation[i][0] = a;
        for(int j = 1; j <= k; ++j) 
            cin >> mutation[i][j];
    }

    vector<vector<int>> antibody(m);
    for(int i = 0; i< m; ++i){
        int k; cin >> k;
        antibody[i].resize(k);
        for(int j = 0; j < k; ++j) cin >> antibody[i][j];
    }

    Trie tri;
    for(auto i: antibody) tri.add(i);
    tri.build_kmp();
    int state_cnt = tri.a.size();
    vector<array<int, 2>> nxt(state_cnt);
    for(int i = 0; i < state_cnt; ++i){
        nxt[i][0] = tri.a[i].nxt[0];
        nxt[i][1] = tri.a[i].nxt[1];
    }

    vector<int> banned;
    for(auto i: antibody){
        int idx = tri.locate(i);
        nxt[idx][0] = nxt[idx][1] = idx;
        banned.push_back(idx);
    }

    vector<int> mutation_list, color_list;
    for(int i = 0; i < n; ++i){
        mutation_list.push_back(-1);
        color_list.push_back(mutation[i][0]);

        bool skip_first = 1;
        for(int j: mutation[i]) {
            if (skip_first){
                skip_first = 0;
                continue;
            }
            mutation_list.push_back(j);
            color_list.push_back(mutation[i][0]);
        }
    }
    mutation_list.push_back(-1);

    for(int i = 0; i < g; ++i) 
    for(int x = 0; x < state_cnt; ++x) for(int y = 0; y < state_cnt; ++y)
        edge[i][x][y] = INF;
    for(int i = 0; i < (int) mutation_list.size(); ++i)
    for(int x = 0; x < state_cnt; ++x) for(int y = 0; y < state_cnt; ++y)
        dp[i][x][y] = INF;

    for(int i = 0; i < (int) mutation_list.size(); ++i) if (mutation_list[i] == -1)
    for(int x = 0; x < state_cnt; ++x) dp[i][x][x] = 0;

    vector<vector<int>> pos(g);
    for(int i = 0; i < (int) mutation_list.size(); ++i) if (mutation_list[i] != -1)
        pos[mutation_list[i]].push_back(i);

    for(int x = 0; x < state_cnt; ++x){
        edge[0][x][nxt[x][0]] = 1;
        edge[1][x][nxt[x][1]] = 1;
    }

    priority_queue<P, vector<P>, compare> pq;
    for(int bit = 0; bit <= 1; ++bit)
    for(int i: pos[bit]){
        for(int x = 0; x < state_cnt; ++x)
        for(int y = 0; y < state_cnt; ++y){
            if (minimize(dp[i][x][nxt[y][bit]], dp[i-1][x][y] + 1)){
                pq.push(P(i, x, nxt[y][bit], dp[i][x][nxt[y][bit]]));
            }
        }
    }

    while(pq.size()){
        P cur = pq.top(); pq.pop();
        int color = color_list[cur.i];
        int i = cur.i, x = cur.j, y = cur.k;
        ll w = cur.w;

        if (mutation_list[i+1] == -1){
            if (minimize(edge[color][x][y], w)){
                for(int j: pos[color]){
                    for(int z = 0; z < state_cnt; ++z){
                        if (minimize(dp[j][z][y], dp[j-1][z][x] + w)){
                            pq.push(P(j, z, y, dp[j][z][y]));
                        }
                    }
                }
            }
        }
        else{
            int next_thing = mutation_list[i+1];
            for(int z = 0; z < state_cnt; ++z){
                if (minimize(dp[i+1][x][z], w + edge[next_thing][y][z])){
                    pq.push(P(i+1, x, z, dp[i+1][x][z]));
                }
            }
        }
    }

    remove_dup(banned);
    for(int i = 2; i < g; ++i){
        ll ans = INF;
        for(int j = 0; j < state_cnt; ++j) if (!binary_search(ALL(banned), j)){
            minimize(ans, edge[i][0][j]);
        }

        if (ans == INF) cout << "YES\n";
        else cout << "NO " << ans << "\n";
    }
}   

int main(void){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

    clock_t start = clock();

    solve();

    cerr << "Time elapsed: " << clock() - start << "ms!\n";
    return 0;
}

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