제출 #595567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
595567		Deepesson	Event Hopping (BOI22_events)	C++17	10 / 100	1585 ms	33804 KiB

events

#include <bits/stdc++.h>
#define MAX 200005
int N,Q;
typedef std::pair<int,int> pii;
std::vector<pii> eventos;

std::vector<int> add[MAX];

std::vector<int> rem[MAX];

int catalogo_avanco[MAX];
bool moscando[MAX];
int visitado[MAX];

void explora(int x){
    memset(&catalogo_avanco,0,sizeof(catalogo_avanco));
    memset(&visitado,0,sizeof(visitado));
    memset(&moscando,0,sizeof(moscando));
    catalogo_avanco[eventos[x].second]=1;
    for(int i=0;i!=MAX;++i){
        for(auto&x:add[i]){
            moscando[x]=true;
        }
        int d = catalogo_avanco[i];
        if(d){
            for(int i=0;i!=N;++i){
                auto& x = moscando[i];
                if(!x)continue;
                if(d){
                    if(!visitado[i])
                        visitado[i]=d+1;
                    else visitado[i]=std::min(visitado[i],d+1);
                }
               // std::cout<<"Visita "<<x.first<<" "<<d<<" "<<i<<"\n";
                if(!catalogo_avanco[eventos[i].second])catalogo_avanco[eventos[i].second]=d+1;
                else
                catalogo_avanco[eventos[i].second]=std::min((int)catalogo_avanco[eventos[i].second],d+1);
            }
        }
        for(auto&x:rem[i]){
            moscando[x]=false;
        }
    }

}

typedef std::pair<int,int*> pipo;

int secao[MAX],periodo[MAX];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>Q;
    for(int i=0;i!=N;++i){
        int a,b;
        std::cin>>a>>b;
        eventos.push_back({a,b});
    }

    {
        std::vector<pipo> comprime;
        for(auto&x:eventos){
            comprime.push_back({x.first,&x.first});
            comprime.push_back({x.second,&x.second});
        }
        std::sort(comprime.begin(),comprime.end());
        int last=-1,cord=1;
        for(auto&x:comprime){
            if(x.first!=last){
                last=x.first;
                ++cord;
            }
            *x.second=cord;
        }
    }
    for(int i=0;i!=N;++i){
        add[eventos[i].first].push_back(i);
        rem[eventos[i].second].push_back(i);
    }

    if(Q<=100){
        for(int i=0;i!=Q;++i){
            int s,e;
            std::cin>>s>>e;--s;--e;
            if(s==e){
                std::cout<<"0\n";
                continue;
            }
            explora(s);
            if(visitado[e]){
                std::cout<<visitado[e]-1<<"\n";
            }else std::cout<<"impossible\n";
        }
    }else {///Linha
        assert(0);
        int count=0;
        int grupos=0;
        int prox=-1;
        for(int i=0;i!=MAX;++i){
            for(auto&x:add[i]){
                if(i!=prox){
                    ++grupos;
                }
                secao[i]=grupos;
                periodo[i]=count;
                ++count;
                prox=eventos[i].second;
            }
        }
        for(int i=0;i!=Q;++i){
            int a,b;
            std::cin>>a>>b;
            --a;--b;
            if(secao[a]!=secao[b]){
                std::cout<<"impossible\n";
                continue;
            }
            int dist = periodo[a]-periodo[b];
            if(dist<0){
                std::cout<<"impossible\n";
                continue;
            }
            std::cout<<dist<<"\n";
        }
    }
}

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

events.cpp: In function 'int main()':
events.cpp:103:22: warning: unused variable 'x' [-Wunused-variable]
  103 |             for(auto&x:add[i]){
      |                      ^

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30