Submission #1106349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106349		Requiem	Viruses (BOI20_viruses)	C++17	0 / 100	2 ms	8952 KiB

Viruses

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "Viruses"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Tóm tắt đề:
- Cho G gene, đánh số từ 0 đến G - 1.
- Cho N thao tác đột biến
Từ gene có chỉ số a, nó sẽ tạo thành 1 chuỗi gene mới có độ dài k x1 x2 x3 ... xk

Ta có M kháng thể ở dạng nhị phân.

VỚi từng số a từ 2 đến G - 1, ta muốn đột biến a cho đến khi:
- a trở thành 1 chuỗi nhị phân
- không chứa 1 chuỗi kháng thể nào.

Với những thằng biến đổi được thì xuất độ dài ngắn nhất
Ngược lại, xuất NO.

Sol chuẩn:
subtask 1 (M = 1):
Bài này ta sẽ giải bằng dijkstra / dp đại loại thế.

Ta xuất phát từ thằng x mà chưa được giải xong ta cập nhật 1 thằng bố của nó.

subtask 3 (M = 1):
Bây giờ có nhiều gene được tạo thành từ 1 con virus nên ta
cần phải decode nó thành 1 trạng thái.

dp_i_st_en: Số thằng đột biến từ gen i, xuất phát ở trạng thái st,
và kết thúc ở trạng thái en.

Giả sử ta có thao tác biến a --> <b1, b2, ..., bk>
dp_a_st_en = dp_b1_st_x1 + dp_b2_x1_x2 + dp_b3_x2_x3 + ... + dp_bk_xk-1_en.

Ta biến đổi như sau: 1 thao tác a --> <b1, b2, ..., bk> có thể
được biến đổi thành a --> <b1, z>
z là 1 gen mới và có khả năng z --> <b2, b3, ..., bk>

Trong trường hợp tệ nhất, số gene vẫn là O(G).

Bây giờ ta có thể chuyển trạng thái mượt mà hơn nhờ vào cái này.
a --> <b1>:
dp_i_st_en = min(dp_i_st_en, dp_b1_st_en).

a --> <b1, b2>:
dp_i_st_en = min(dp_i_st_en, di_b1_st_x1 + dp_b2_x1_en)

Nếu ta imple được cái thuật này thì độ phức tạp của nó sẽ là:
- Ta có O(S^2 * G) trạng thái
- Để chuyển trạng thái cho thằng kia, ta cần thêm 1 vòng for S nữa nên độ phức tạp là:
O(S^3 * G * log2(G * S^2)) nếu ta dijkstra.

Thế cái state ở đây là gì: state ở đây là độ khớp với 1 prefix của thằng kháng nguyên,
tức là ta muốn biết là ở độ khớp hiện tại.

Ta gọi dp_i_st_en: độ dài tối thiểu của con virus sao cho nó bắt đầu ở trạng thái khớp
tiền tố st của thằng antibody và kết thúc ở trạng thái khớp tiền tố độ dài l của thằng antibody.
**/

const int MAXN = 301;
int numGene = 0;
int numMutation = 0;
int numAntibody = 0;

int head[MAXN];

vector<int> mutation[MAXN];
vector<int> origin[MAXN];

string antibody[MAXN];

namespace subtask1{
    bool check(){
        return numAntibody == 0;
    }

    unsigned long long dp[MAXN];

    void solve(){
        FOR(i, 1, numMutation){
            for(auto p: mutation[i]){
                origin[p].pb(i);
            }
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[1] = 1;
        dp[0] = 1;
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.push({1, 1});
        pq.push({1, 0});

        while(!pq.empty()){
            int du = pq.top().fi;
            int u = pq.top().se;
            pq.pop();

            if (du > dp[u]) continue;

            for(auto id: origin[u]){
                int a = head[id];
                int cur = 0;

                for(auto b: mutation[id]){
                    cur += dp[b];
                }

                if (minimize(dp[a], (ull) cur)){
                    pq.push({dp[a], a});
                }
            }
        }

        FOR(i, 2, numGene - 1){
            if (dp[i] < inf) cout << dp[i] << endl;
            else cout << "0" << endl;
        }
    }
}

namespace subtask3{
    bool check(){
        return numAntibody == 1;
    }

    ull dp[MAXN][51][51];
    int lps[MAXN], automata[MAXN][2];

    struct state{
        int id, st, en;
        int val;
        state(int _val = 0, int _id = 0, int _st = 0, int _en = 0){
            val = _val, st = _st, en = _en, id = _id;
        }
        bool operator < (const state &other) const {
            return val < other.val;
        }
    };

    void buildKMP(){
        int len = antibody[1].length();
        string anti = antibody[1];
        anti = '#' + anti + '#';

        FOR(i, 2, len){
            int j = lps[i - 1];
            while(j > 0 and anti[j + 1] != anti[i]) j = lps[j];

            if (anti[j + 1] == anti[i]) lps[i] = j + 1;
        }

        FOR(i, 0, len){
            FOR(c, 0, 1){
                if (anti[i + 1] - '0' == c) automata[i][c] = i + 1;
                else automata[i][c] = automata[lps[i]][c];
            }
        }
    }


    void solve(){
        set<pair<ii, ii>> pq;
        memset(dp, 0x3f, sizeof(dp));
        buildKMP();
        int tmp = numGene;

        FOR(i, 1, numMutation){
            while(mutation[i].size() > 2){
                int x2 = mutation[i].back();
                mutation[i].pop_back();
                int x1 = mutation[i].back();
                mutation[i].pop_back();

                mutation[++numMutation].pb(x1);
                mutation[numMutation].pb(x2);
                head[numMutation] = ++numGene;
                mutation[i].pb(numGene);
            }
        }
        FOR(i, 1, numMutation){
            for(int j = 0; j < mutation[i].size(); j++){
                origin[mutation[i][j]].pb(i);
            }
        }

        FOR(i, 0, 1){
            FOR(st, 0, antibody[1].length() - 1){
                int en = automata[st][i];
                if (en < antibody[1].length()) {
                    dp[i][st][en] = 1;
                    pq.insert({{1, i}, {st, en}});
                }
            }
        }
        int complexity = 0;
        while(!pq.empty()){
            pair<ii, ii> tp = *pq.begin();
            int u = tp.fi.se;
            int st = tp.se.fi;
            int en = tp.se.se;

            int du = tp.fi.fi;

            pq.erase(pq.begin());

            if (du > dp[u][st][en]) continue;
            complexity++;

            for(auto id: origin[u]){
                int a = head[id];
                if (mutation[id].size() == 1){
                    if (minimize(dp[a][st][en],(ull) du))
                        pq.insert({{du, a}, {st, en}});
                }
                else{
                    int other = ((mutation[id][0] == u) ? mutation[id][1] : mutation[id][0]);
                    FOR(third, 0, antibody[1].length() - 1){
                        if (mutation[id][0] == u) {

                            if (minimize(dp[a][st][third],(ull) du + dp[other][en][third])){
                                if (pq.find({{dp[a][st][third], a}, {st, third}}) == pq.end())
                                    pq.insert({{dp[a][st][third], a}, {st, third}});
                            }
                        }

                        if (mutation[id][1] == u){
                            if (minimize(dp[a][third][en], (ull) dp[other][third][st] + du)){
                                if (pq.find({{dp[a][third][en], a}, {third, en}}) == pq.end())
                                    pq.insert({{dp[a][third][en], a}, {third, en}});
                            }
                        }
                    }
                }
            }

        }
        FOR(i, 2, tmp - 1){
            ull ans = inf + 1;
            FOR(j, 0, (int) antibody[1].length() - 1){
                minimize(ans, dp[i][0][j]);
            }
            if (ans < inf) cout << ans << endl;
            else cout << "0\n";
        }

    }
}

namespace subtask5{
    bool check(){
        return true;
    }

    struct TrieNode{
        int child[2], suffixLink, depth, parent, bad;
        int automata[2];
        TrieNode(){
            suffixLink = 0;
            parent = 0;
            depth = 0;
            bad = false;
            memset(child, 0, sizeof(child));
            memset(automata, 0, sizeof(automata));
        }
    };

    struct Trie{
        vector<TrieNode> T = {TrieNode()};
        void addNum(string str){
            int p = 0;
            for(int i = 0; i < (int) str.length(); i++){
                int c = str[i] - '0';
                if (T[p].child[c] == 0){
                    T[p].child[c] = T.size();
                    T.pb(TrieNode());
                }

                T[T[p].child[c]].depth = T[p].depth + 1;
                T[T[p].child[c]].parent = p;

                p = T[p].child[c];
            }
            T[p].bad = true;
        }

        void constructAC(){
            queue<ii> q;
            q.push({0, -1});

            while(!q.empty()){
                int u = q.front().fi;
                int c = q.front().se;
                q.pop();

                if (T[u].depth <= 1) {
                    T[u].suffixLink = 0;
                }
                else{
                    int prv = T[T[u].parent].suffixLink;
                    while(prv > 0 and T[prv].child[c] == 0){
                        prv = T[prv].suffixLink;
                    }
                    if (T[prv].child[c] != 0) T[u].suffixLink = T[prv].child[c];
                }
                T[u].automata[0] = ((T[u].child[0] > 0) ? (T[u].child[0]) : (T[T[u].suffixLink].automata[0]));
                T[u].automata[1] = ((T[u].child[1] > 0) ? (T[u].child[1]) : (T[T[u].suffixLink].automata[1]));
                T[u].bad |= T[T[u].parent].bad;
                T[u].bad |= T[T[u].suffixLink].bad; //1 tien to la te khi ma chua 1 tien to khac le te.

                for(int i = 0; i < 2; i++){
                    if (T[u].child[i] > 0) q.push({T[u].child[i], i});
                }
            }
        }


    };

    ull dp[MAXN][59][59];
    void solve(){
         Trie Trie;
         FOR(i, 1, numAntibody){
             Trie.addNum(antibody[i]);
         }
         Trie.constructAC();

         int tmp = numGene;
         FOR(i, 1, numMutation){
             while(mutation[i].size() > 2){
                   int x2 = mutation[i].back();
                   mutation[i].pop_back();
                   int x1 = mutation[i].back();
                   mutation[i].pop_back();

                   mutation[++numMutation].pb(x1);
                   mutation[numMutation].pb(x2);

                   head[numMutation] = ++numGene;
                   mutation[i].pb(numGene);
             }
         }

         FOR(i, 1, numMutation){
             FOR(j, 0, (int) mutation[i].size() - 1){
                 origin[mutation[i][j]].pb(i);
             }
         }

         memset(dp, 0x3f, sizeof(dp));
         priority_queue<pair<ii, ii>, vector<pair<ii, ii>>, greater<pair<ii, ii>>> pq;

         FOR(i, 0, 1){
             FOR(j, 0, (int) Trie.T.size() - 1){
                if (Trie.T[j].bad) continue;

                int st = j;
                int en = Trie.T[j].automata[i];

                if (Trie.T[en].bad) continue;

                pq.push({{1,i} , {st,en}});
                dp[i][st][en] = 1;
             }
         }

         while(!pq.empty()){
             pair<ii, ii> tp = pq.top();
             int u = tp.fi.se;
             int st = tp.se.fi;
             int en = tp.se.se;
             int du = tp.fi.fi;
             pq.pop();

             if (du > dp[u][st][en]) continue;

             for(auto id: origin[u]){
                 int a = head[id];

                 if (mutation[id].size() == 1){
                     if (minimize(dp[a][st][en], (ull) du)){
                         pq.push({{dp[a][st][en], a}, {st, en}});
                     }
                 }
                 else {
                     int other = ((mutation[id][0] == u) ? mutation[id][1] : mutation[id][0]);

                     FOR(third, 0, Trie.T.size() - 1){
                         if (mutation[id][0] == u){
                             if (minimize(dp[a][st][third], (ull) du + dp[other][en][third])){
                                 pq.push({ {dp[a][st][third], a} , {st, third} });
                             }
                         }

                         if (mutation[id][1] == u){
                             if (minimize(dp[a][third][en], (ull) dp[other][third][st] + du)){
                                 pq.push({  {dp[a][third][en], a}, {third, en} });
                             }
                         }
                     }
                 }
             }
         }


         FOR(i, 2, tmp - 1){
             ull ans = inf;
             FOR(j, 0, (int) Trie.T.size() - 1){
                 minimize(ans, dp[i][0][j]);
             }
             if (ans < inf) cout << ans << endl;
             else cout << 0 << endl;

         }


    }
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> numGene >> numMutation >> numAntibody;
    FOR(i, 1, numMutation){
        int a;
        int k;
        cin >> a >> k;
        head[i] = a;
        FOR(j, 0, k - 1){
            int x;
            cin >> x;
            mutation[i].pb(x);
        }
    }

    FOR(i, 1, numAntibody){
        int x;
        cin >> x;
        FOR(j, 0, x - 1){
            char c;
            cin >> c;
            antibody[i] = antibody[i] + c;
        }
    }

   // if (subtask1::check()) return subtask1::solve(), 0;
   // if (subtask3::check()) return subtask3::solve(), 0;
    if (subtask5::check()) return subtask5::solve(), 0;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message (stderr)

Viruses.cpp: In function 'void subtask1::solve()':
Viruses.cpp:115:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  115 |             if (du > dp[u]) continue;
      |                 ~~~^~~~~~~
Viruses.cpp: In function 'void subtask3::solve()':
Viruses.cpp:198:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |             for(int j = 0; j < mutation[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
  204 |             FOR(st, 0, antibody[1].length() - 1){
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:204:13: note: in expansion of macro 'FOR'
  204 |             FOR(st, 0, antibody[1].length() - 1){
      |             ^~~
Viruses.cpp:206:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |                 if (en < antibody[1].length()) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:223:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  223 |             if (du > dp[u][st][en]) continue;
      |                 ~~~^~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
  234 |                     FOR(third, 0, antibody[1].length() - 1){
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:234:21: note: in expansion of macro 'FOR'
  234 |                     FOR(third, 0, antibody[1].length() - 1){
      |                     ^~~
Viruses.cpp: In function 'void subtask5::solve()':
Viruses.cpp:391:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  391 |              if (du > dp[u][st][en]) continue;
      |                  ~~~^~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subtask5::TrieNode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
  404 |                      FOR(third, 0, Trie.T.size() - 1){
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:404:22: note: in expansion of macro 'FOR'
  404 |                      FOR(third, 0, Trie.T.size() - 1){
      |                      ^~~
Viruses.cpp: At global scope:
Viruses.cpp:435:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  435 | main()
      | ^~~~
Viruses.cpp: In function 'int main()':
Viruses.cpp:439:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  439 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:440:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  440 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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