oj.uz

답안 #577736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577736 2022-06-15T08:28:54 Z vanic Event Hopping (BOI22_events) C++14
0 / 100
 1500 ms 26224 KB 
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <queue>
 
using namespace std;
 
const int maxn=1e5+5, Log=17, pot=(1<<Log);
 
vector < int > svi;
 
void query(int L, int D, int x, int l, int d){
	if(L>=l && D<=d){
		svi.push_back(x);
		return;
	}
	if((L+D)/2>=l){
		query(L, (L+D)/2, x*2, l, d);
	}
	if((L+D)/2+1<=d){
		query((L+D)/2+1, D, x*2+1, l, d);
	}
}
 
 
pair < int, int > a[maxn];
set < int > s;
map < int, int > m;
int dist[pot*2];
int d[maxn];
vector < pair < int, int > >  ms[pot*2];
 
void precompute(){
	for(int i=2; i<pot*2; i++){
		ms[i].push_back({i/2, 0});
	}
}
 
void bfs(int x){
	memset(dist, -1, sizeof(dist));
	memset(d, -1, sizeof(d));
	deque < int > q;
	q.push_front(a[x].second+pot);
	dist[a[x].second+pot]=0;
	d[x]=0;
	int tren=0;
	while(!q.empty()){
		x=q.front();
		q.pop_front();
		for(int i=0; i<(int)ms[x].size(); i++){
			if(ms[x][i].second){
				if(dist[ms[x][i].first]==-1){
					dist[ms[x][i].first]=tren+1;
					q.push_back(ms[x][i].first);
				}
				if(d[ms[x][i].second]==-1){
					d[ms[x][i].second]=tren+1;
				}
			}
			else{
				if(dist[ms[x][i].first]==-1){
					dist[ms[x][i].first]=tren;
					q.push_front(ms[x][i].first);
				}
			}
		}
		tren++;
	}
}
 
int main(){
	precompute();
	int n, q;
	scanf("%d%d", &n, &q);
	for(int i=1; i<=n; i++){
		scanf("%d%d", &a[i].first, &a[i].second);
		s.insert(a[i].second);
	}
	int br=0;
	
	for(auto it=s.begin(); it!=s.end(); it++){
		m[*it]=br;
		br++;
	}
	set < int >::iterator it;
	for(int i=1; i<=n; i++){
		it=s.lower_bound(a[i].first);
		a[i]={m[*it], m[a[i].second]};
//		cout << a[i].first << ' ' << a[i].second << endl;
		query(0, pot-1, 1, a[i].first, a[i].second);
		while(!svi.empty()){
//			cout << "moji " << svi.back() << endl;
			ms[svi.back()].push_back({a[i].second+pot, i});
			svi.pop_back();
		}
	}
	int x, y;
	for(int i=0; i<q; i++){
		scanf("%d%d", &x, &y);
		bfs(x);
		if(d[y]==-1){
			printf("impossible\n");
		}
		else{
			printf("%d\n", d[y]);
		}
	}
	return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
events.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d%d", &a[i].first, &a[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 16044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 16044 KB Output isn't correct
2 Halted 0 ms 0 KB -