제출 #548982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548982		Deepesson	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	879 ms	467916 KiB

bitaro

#include <bits/stdc++.h>
#define MAX 505000
#define SQRT 450
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){

        for(auto&x:con[i])
            data[x]=0;

        for(int j=0;j!=SQRT+5;++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 || (opcao.first==melhor.first && rand()%2)){
                    melhor=opcao;
                    split=x;
                }
            }
            if(melhor.first==-1)break;
            ++data[split];

            besto[i].push_back(melhor);
        }

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

        for(auto&x:queries[i]){
            int ansr=-1;
            for(auto&z:besto[i]){
                if(combs[x].find(z.second)!=combs[x].end())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;
        if(!B){
            queries[S].push_back(i);
            continue;
        }
        int array[B];
        for(int j=0;j!=B;++j){
            std::cin>>array[j];
            --array[j];
        }
        if(B>=200){///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";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'void processa_slow()':
bitaro.cpp:35: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]
   35 |                 if(data[x]==besto[x].size())continue;
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~

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