Submission #551877

#	Time	Username	Problem	Language	Result	Execution time	Memory
551877		Deepesson	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1522 ms	442176 KiB

bitaro

#include <bits/stdc++.h>
#define MAX 105000
#define SQRT 500
typedef std::pair<int,int> pii;
int N,M,Q;
std::vector<int> con[MAX];
long long ans[MAX]={};
long long processa(int fim,int B,int* bloqueia){
    memset(ans,0,sizeof(ans));
    for(int i=0;i!=B;++i)ans[bloqueia[i]]=-(1e9+7);
    for(int i=0;i!=fim+1;++i){
        for(auto&x:con[i]){
            ans[i]=std::max(ans[i],ans[x]+1);
        }
    }
    return std::max(-1LL,ans[fim]);
}
int resp[MAX];
std::vector<int> queries[MAX];
std::map<int,bool> combs[MAX];
std::vector<pii> besto[MAX];
long long data[MAX];
int rod[MAX];
int turno=42;
void processa_slow(void)
{
    for(int i=0;i!=N+1;++i){

        for(auto&x:con[i])
            data[x]=0;
        turno+=3;
        for(int j=0;j!=SQRT;++j){
            pii melhor={-1,-1};
            int split=0;
            for(auto&x:con[i]){
                inicio:
                if(data[x]>=besto[x].size())continue;
                if(rod[besto[x][data[x]].second]==turno){++data[x];goto inicio;}
                pii opcao;
                opcao={besto[x][data[x]].first+1,besto[x][data[x]].second};
                if(opcao.first>melhor.first){
                    melhor=opcao;
                    split=x;
                }
            }
            if(melhor.first==-1)break;
            ++data[split];
            rod[melhor.second]=turno;
            besto[i].push_back(melhor);
        }

        besto[i].push_back({0,i});

        for(auto&x:queries[i]){
            for(auto&z:besto[i]){
                if(combs[x].find(z.second)!=combs[x].end())continue;
                resp[x]=std::max(resp[x],z.first);
                goto nextstep;
            }
            resp[x]=-1;
            nextstep:{}
        }

    }

}
int array[MAX];
int main()
{
   /// freopen("03-125.txt", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>M>>Q;
    std::map<pii,bool> canal;
    for(int i=0;i!=M;++i){
        int S,E;
        std::cin>>S>>E;
        --S;--E;
        canal[{S,E}]=true;
    }
    for(auto&x:canal){
        con[x.first.second].push_back(x.first.first);
    }
    for(int i=0;i!=Q;++i){
        int S,B;
        std::cin>>S>>B;--S;
        for(int j=0;j!=B;++j){
            std::cin>>array[j];
            --array[j];
        }
        if(B>=450){///Forca Bruta
            resp[i]=processa(S,B,array);
        }else {///SQRT melhores respostas
            for(int j=0;j!=B;++j){
                combs[i][array[j]]=true;
            }
            queries[S].push_back(i);
        }
    }

    processa_slow();

    for(int i=0;i!=Q;++i){
        std::cout<<resp[i]<<"\n";
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'void processa_slow()':
bitaro.cpp:37:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                 if(data[x]>=besto[x].size())continue;
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86