oj.uz

답안 #603002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603002 2022-07-23T14:07:22 Z DanerZein Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 30616 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1583 ms 3720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 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 -