# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
595538 | Sofiatpc | Event Hopping (BOI22_events) | C++14 | 1586 ms | 32816 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int s[MAXN], e[MAXN], dist[MAXN];
vector<int> adj[MAXN];
void bfs(int S)//S eh um id
{
vector< int > fila;
dist[S]=0;
fila.push_back(S);
int ptr = 0;
while(ptr!=fila.size())
{
int x = fila[ptr];
ptr++;
for(int i = 0; i < (int)adj[x].size(); i++)
{
int viz=adj[x][i];
if(dist[viz]!=-1&&dist[viz]<=dist[x]+1)continue;
dist[viz]=dist[x]+1;
fila.push_back(viz);
}
}
}
int main()
{
int N,Q; cin>>N>>Q;
for(int i = 1; i <= N; i++)cin>>s[i]>>e[i];
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
{
if(i==j)continue;
if(s[j]<=e[i] && e[i]<=e[j])adj[i].push_back(j);
}
for(int q = 1; q <= Q; q++)
{
int sx,ex;
cin>>sx>>ex;
for(int i = 1; i <= N; i++)dist[i]=-1;
bfs(sx);
if(dist[ex]==-1)cout<<"impossible\n";
else cout<<dist[ex]<<"\n";
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |