Submission #603002

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
603002	2022-07-23T14:07:22 Z	DanerZein	Event Hopping (BOI22_events)	C++14	10 / 100	1500 ms	30616 KB

events

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
const int MAX_N=1e5+10;
const int MAX=1e9;
vector<vi> G;
vii ev;
int dis[MAX_N];
int n;
bool isq[MAX_N];
void bfs(int u){
  for(int i=0;i<n;i++) dis[i]=MAX;
  dis[u]=0; isq[u]=1;
  queue<int> q; q.push(u);
  while(!q.empty()){
    int x=q.front(); q.pop();
    isq[x]=0;
    for(auto &v:G[x]){
      if(dis[v]>dis[x]+1){
	dis[v]=dis[x]+1;
	if(!isq[v]){
	  isq[v]=1;
	  q.push(v);
	}
      }
    }
  }
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int q; cin>>n>>q;
  for(int i=0;i<n;i++){
    int a,b; cin>>a>>b;
    ev.push_back(ii(a,b));
  }
  G.resize(n+1);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(ev[j].first<=ev[i].second && ev[i].second<=ev[j].second){
	G[i].push_back(j);
      }
    }
  }
  while(q--){
    int s,e; cin>>s>>e;
    s--; e--;
    bfs(s);
    if(dis[e]>=MAX) cout<<"impossible\n";
    else cout<<dis[e]<<endl;
  }
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Execution timed out	1567 ms	3680 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	7 ms	340 KB	Output is correct
4	Correct	6 ms	340 KB	Output is correct
5	Correct	6 ms	340 KB	Output is correct
6	Correct	9 ms	1108 KB	Output is correct
7	Correct	17 ms	2004 KB	Output is correct
8	Correct	18 ms	3028 KB	Output is correct
9	Correct	69 ms	4308 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	7 ms	340 KB	Output is correct
4	Correct	6 ms	340 KB	Output is correct
5	Correct	6 ms	340 KB	Output is correct
6	Correct	9 ms	1108 KB	Output is correct
7	Correct	17 ms	2004 KB	Output is correct
8	Correct	18 ms	3028 KB	Output is correct
9	Correct	69 ms	4308 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	7 ms	340 KB	Output is correct
13	Correct	5 ms	340 KB	Output is correct
14	Correct	6 ms	340 KB	Output is correct
15	Correct	9 ms	1108 KB	Output is correct
16	Correct	16 ms	2004 KB	Output is correct
17	Correct	17 ms	3028 KB	Output is correct
18	Correct	68 ms	4400 KB	Output is correct
19	Execution timed out	1556 ms	30616 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	7 ms	340 KB	Output is correct
4	Correct	6 ms	340 KB	Output is correct
5	Correct	6 ms	340 KB	Output is correct
6	Correct	9 ms	1108 KB	Output is correct
7	Correct	17 ms	2004 KB	Output is correct
8	Correct	18 ms	3028 KB	Output is correct
9	Correct	69 ms	4308 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	7 ms	340 KB	Output is correct
13	Correct	7 ms	340 KB	Output is correct
14	Correct	6 ms	396 KB	Output is correct
15	Correct	9 ms	1180 KB	Output is correct
16	Correct	18 ms	1876 KB	Output is correct
17	Correct	18 ms	3044 KB	Output is correct
18	Correct	72 ms	4308 KB	Output is correct
19	Execution timed out	1569 ms	3548 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1583 ms	3720 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Execution timed out	1567 ms	3680 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-