Submission #548971

#	Time	Username	Problem	Language	Result	Execution time	Memory
548971		Deepesson	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1173 ms	467808 KiB

bitaro

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

        for(auto&x:con[i]){
            count+=besto[x].size();
            data[x]=0;
        }

        for(int j=0;j!=std::min(SQRT+5,count);++j){
            pii melhor={-1,-1};
            int split=0;
            for(auto&x:con[i]){
                if(data[x]==besto[x].size())continue;
                pii opcao;
                opcao={besto[x][data[x]].first+1,besto[x][data[x]].second};
                if(opcao.first>=melhor.first){
                    melhor=opcao;
                    split=x;
                }
            }
            ++data[split];
            assert(melhor.first!=-1);
            besto[i].push_back(melhor);
        }

        if(count<=SQRT+5)
            besto[i].push_back({0,i});

        for(auto&x:queries[i]){
            int ansr=-1;
            for(auto&z:besto[i]){
                if(combs[x][z.second])continue;
                ansr=z.first;
                break;
            }
            resp[x]=ansr;
        }

    }

}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>M>>Q;
    for(int i=0;i!=M;++i){
        int S,E;
        std::cin>>S>>E;
        --S;--E;
        con[E].push_back(S);
    }
    for(int i=0;i!=Q;++i){
        int S,B;
        std::cin>>S>>B;--S;
        int array[B];for(auto&x:array){std::cin>>x;--x;}
        if(B>=30){///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:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 if(data[x]==besto[x].size())continue;
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~

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