Submission #1204755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204755		Unforgettablepl	Viruses (BOI20_viruses)	C++20	14 / 100	1 ms	328 KiB

Viruses

#include <bits/stdc++.h>
using namespace std;

#define int long long

const unsigned int INF = ((unsigned int)1<<63);


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int G,N,M;
    cin >> G >> N >> M;
    vector<vector<vector<int>>> mutations(G);
    for(int i=1;i<=N;i++){
        int a,k;
        cin >> a >> k;
        for(int&x:mutations[a].emplace_back(k))cin>>x;
    }
    vector<vector<int>> antibodies;
    vector<__int128> bad = {2};
    auto combine = [&](vector<__int128> &seqA,vector<__int128> &seqB){
        if(!seqA.empty() and seqA[0]==2)return bad;
        if(!seqB.empty() and seqB[0]==2)return bad;
        vector<__int128> seqC=seqA;
        for(__int128&i:seqB)seqC.emplace_back(i);
        bool isBad=false;
        for(int i=0;i<seqC.size();i++){
            for(auto&antibody:antibodies){
                if(i+antibody.size()>seqC.size())continue;
                bool works = true;
                for(int j=0;j<antibody.size();j++){
                    if((__int128)antibody[j]!=seqC[i+j]){
                        works=false;
                        break;
                    }
                }
                if(!works)continue;
                isBad=true;
                break;
            }
            if(isBad)break;
        }
        __int128 middleLength = 0;
        for(int i=50;i<(int)seqC.size()-50;i++){
            if(seqC[i]>=0)middleLength++;
            else middleLength+=-seqC[i];
        }
        if(isBad){
            return bad;
        }
        middleLength = -middleLength;
        if(middleLength!=0){
            vector<__int128> seqAns;
            for(int i=0;i<50;i++){
                seqAns.emplace_back(seqC[i]);
            }
            seqAns.emplace_back(middleLength);
            for(int i=seqC.size()-50;i<seqC.size();i++){
                seqAns.emplace_back(seqC[i]);
            }
            return seqAns;
        } else return seqC;
    };
    for(int i=1;i<=M;i++){
        int l;
        cin >> l;
        for(int&x:antibodies.emplace_back(l))cin>>x;
    }
    vector<vector<__int128>> ans(G);
    {
        // Solving M==0
        ans[0]={0};
        ans[1]={1};
        vector<int> visited(G);
        visited[0]=visited[1]=2;
        auto dfs = [&](auto&& self,int x)->void{
            if(visited[x]){
                if(visited[x]==1){
                    ans[x]={2};
                }
                return;
            }
            visited[x]=1;
            auto mutation = mutations[x][0];
            for(int&i:mutation){
                self(self,i);
                ans[x]=combine(ans[x],ans[i]);
            }
            visited[x]=2;
        };
        for(int i=2;i<G;i++){
            if(!visited[i])dfs(dfs,i);
            __int128 lenAns = 0;
            for(auto&i:ans[i]){
                if(i>=0)lenAns++;
                else lenAns+=-i;
            }
            if(ans[i][0]==2 or lenAns>=INF)cout<<"YES\n";
            else cout << "NO " << (int)lenAns << '\n';
        }
    }
}

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