oj.uz

Submission #595566

# Submission time Handle Problem Language Result Execution time Memory
595566 2022-07-13T20:25:24 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 19860 KB 
#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
        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";
        }
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11476 KB Output is correct
2 Incorrect 87 ms 19576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11480 KB Output is correct
2 Correct 8 ms 11476 KB Output is correct
3 Correct 109 ms 11552 KB Output is correct
4 Correct 81 ms 11552 KB Output is correct
5 Correct 103 ms 11548 KB Output is correct
6 Correct 87 ms 11548 KB Output is correct
7 Correct 177 ms 11476 KB Output is correct
8 Correct 164 ms 11548 KB Output is correct
9 Correct 65 ms 11540 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11480 KB Output is correct
2 Correct 8 ms 11476 KB Output is correct
3 Correct 109 ms 11552 KB Output is correct
4 Correct 81 ms 11552 KB Output is correct
5 Correct 103 ms 11548 KB Output is correct
6 Correct 87 ms 11548 KB Output is correct
7 Correct 177 ms 11476 KB Output is correct
8 Correct 164 ms 11548 KB Output is correct
9 Correct 65 ms 11540 KB Output is correct
10 Correct 7 ms 11476 KB Output is correct
11 Correct 10 ms 11476 KB Output is correct
12 Correct 116 ms 11556 KB Output is correct
13 Correct 77 ms 11552 KB Output is correct
14 Correct 97 ms 11476 KB Output is correct
15 Correct 83 ms 11548 KB Output is correct
16 Correct 164 ms 11552 KB Output is correct
17 Correct 150 ms 11548 KB Output is correct
18 Correct 67 ms 11476 KB Output is correct
19 Incorrect 28 ms 11560 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11480 KB Output is correct
2 Correct 8 ms 11476 KB Output is correct
3 Correct 109 ms 11552 KB Output is correct
4 Correct 81 ms 11552 KB Output is correct
5 Correct 103 ms 11548 KB Output is correct
6 Correct 87 ms 11548 KB Output is correct
7 Correct 177 ms 11476 KB Output is correct
8 Correct 164 ms 11548 KB Output is correct
9 Correct 65 ms 11540 KB Output is correct
10 Correct 7 ms 11440 KB Output is correct
11 Correct 8 ms 11476 KB Output is correct
12 Correct 116 ms 11544 KB Output is correct
13 Correct 81 ms 11476 KB Output is correct
14 Correct 91 ms 11540 KB Output is correct
15 Correct 90 ms 11552 KB Output is correct
16 Correct 157 ms 11548 KB Output is correct
17 Correct 152 ms 11552 KB Output is correct
18 Correct 65 ms 11544 KB Output is correct
19 Execution timed out 1557 ms 18984 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 19860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11476 KB Output is correct
2 Incorrect 87 ms 19576 KB Output isn't correct
3 Halted 0 ms 0 KB -