oj.uz

Submission #577675

# Submission time Handle Problem Language Result Execution time Memory
577675 2022-06-15T07:57:28 Z vanic Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 524288 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));
	queue < int > q1, q2;
	q1.push(a[x].second+pot);
	dist[a[x].second+pot]=0;
	d[x]=0;
	int tren=0;
	while(!q1.empty()){
		while(!q1.empty()){
			x=q1.front();
			q1.pop();
			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(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(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].first);
		s.insert(a[i].second);
	}
	int br=0;
	for(auto it=s.begin(); it!=s.end(); it++){
		m[*it]=br;
		br++;
	}
	for(int i=1; i<=n; i++){
		a[i]={m[a[i].first], 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:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
events.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d%d", &a[i].first, &a[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15956 KB Output is correct
2 Execution timed out 1588 ms 26220 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15956 KB Output is correct
2 Correct 17 ms 15956 KB Output is correct
3 Correct 27 ms 16084 KB Output is correct
4 Correct 22 ms 16176 KB Output is correct
5 Correct 23 ms 16096 KB Output is correct
6 Correct 22 ms 16212 KB Output is correct
7 Correct 25 ms 16340 KB Output is correct
8 Correct 31 ms 16336 KB Output is correct
9 Correct 20 ms 16048 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15956 KB Output is correct
2 Correct 17 ms 15956 KB Output is correct
3 Correct 27 ms 16084 KB Output is correct
4 Correct 22 ms 16176 KB Output is correct
5 Correct 23 ms 16096 KB Output is correct
6 Correct 22 ms 16212 KB Output is correct
7 Correct 25 ms 16340 KB Output is correct
8 Correct 31 ms 16336 KB Output is correct
9 Correct 20 ms 16048 KB Output is correct
10 Correct 16 ms 16068 KB Output is correct
11 Correct 16 ms 15956 KB Output is correct
12 Correct 24 ms 16156 KB Output is correct
13 Correct 21 ms 16084 KB Output is correct
14 Correct 23 ms 16084 KB Output is correct
15 Correct 21 ms 16148 KB Output is correct
16 Correct 28 ms 16360 KB Output is correct
17 Correct 26 ms 16340 KB Output is correct
18 Correct 21 ms 16092 KB Output is correct
19 Execution timed out 1597 ms 17276 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15956 KB Output is correct
2 Correct 17 ms 15956 KB Output is correct
3 Correct 27 ms 16084 KB Output is correct
4 Correct 22 ms 16176 KB Output is correct
5 Correct 23 ms 16096 KB Output is correct
6 Correct 22 ms 16212 KB Output is correct
7 Correct 25 ms 16340 KB Output is correct
8 Correct 31 ms 16336 KB Output is correct
9 Correct 20 ms 16048 KB Output is correct
10 Correct 16 ms 15956 KB Output is correct
11 Correct 17 ms 15976 KB Output is correct
12 Correct 25 ms 16084 KB Output is correct
13 Correct 22 ms 16084 KB Output is correct
14 Correct 24 ms 16144 KB Output is correct
15 Correct 22 ms 16084 KB Output is correct
16 Correct 31 ms 16340 KB Output is correct
17 Correct 24 ms 16420 KB Output is correct
18 Correct 21 ms 16004 KB Output is correct
19 Correct 1027 ms 26256 KB Output is correct
20 Correct 703 ms 26232 KB Output is correct
21 Correct 856 ms 31500 KB Output is correct
22 Runtime error 333 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15956 KB Output is correct
2 Execution timed out 1588 ms 26220 KB Time limit exceeded
3 Halted 0 ms 0 KB -