제출 #577766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577766		vanic	Event Hopping (BOI22_events)	C++14	10 / 100	1587 ms	41760 KiB

events

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
 
using namespace std;
 
const int maxn=1e5+5;
 
vector < int > svi;
 
void query(int l, int d){
	for(l+=maxn, d+=maxn; l<d; l>>=1, d>>=1){
		if(l&1){
			svi.push_back(l++);
		}
		if(d&1){
			svi.push_back(--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[maxn*2];
int d[maxn];
vector < pair < int, int > >  ms[maxn*2];
 
void precompute(){
	for(int i=2; i<maxn*2; i++){
		ms[i].push_back({i/2, 0});
	}
}
 
void bfs(int x){
	memset(dist, -1, sizeof(dist));
	memset(d, -1, sizeof(d));
	vector < int > q1, q2;
	q1.push_back(a[x].second+maxn);
	dist[a[x].second+maxn]=0;
	d[x]=0;
	int tren=0;
	while(!q1.empty()){
		while(!q1.empty()){
			x=q1.back();
			q1.pop_back();
			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;
						q2.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;
						q1.push_back(ms[x][i].first);
					}
				}
			}
		}
		swap(q1, q2);
		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(a[i].first, a[i].second+1);
		while(!svi.empty()){
//			cout << "moji " << svi.back() << endl;
			ms[svi.back()].push_back({a[i].second+maxn, 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30