oj.uz

Submission #577692

# Submission time Handle Problem Language Result Execution time Memory
577692 2022-06-15T08:08:25 Z vanic Event Hopping (BOI22_events) C++14
25 / 100
 1302 ms 203920 KB 
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <queue>

using namespace std;

const int maxn=5005, Log=14, 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];
int ok[maxn][maxn];

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(){
	memset(ok, -1, sizeof(ok));
	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);
		if(ok[x][x]==-1){
			bfs(x);
			for(int j=1; j<=n; j++){
				ok[x][j]=d[j];
			}
		}
		if(ok[x][y]==-1){
			printf("impossible\n");
		}
		else{
			printf("%d\n", ok[x][y]);
		}
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100144 KB Output is correct
2 Runtime error 120 ms 203920 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 100180 KB Output is correct
2 Correct 41 ms 100264 KB Output is correct
3 Correct 41 ms 100268 KB Output is correct
4 Correct 41 ms 100340 KB Output is correct
5 Correct 46 ms 100292 KB Output is correct
6 Correct 45 ms 100284 KB Output is correct
7 Correct 47 ms 100460 KB Output is correct
8 Correct 47 ms 100548 KB Output is correct
9 Correct 40 ms 100184 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 100180 KB Output is correct
2 Correct 41 ms 100264 KB Output is correct
3 Correct 41 ms 100268 KB Output is correct
4 Correct 41 ms 100340 KB Output is correct
5 Correct 46 ms 100292 KB Output is correct
6 Correct 45 ms 100284 KB Output is correct
7 Correct 47 ms 100460 KB Output is correct
8 Correct 47 ms 100548 KB Output is correct
9 Correct 40 ms 100184 KB Output is correct
10 Correct 39 ms 100180 KB Output is correct
11 Correct 44 ms 100240 KB Output is correct
12 Correct 44 ms 100300 KB Output is correct
13 Correct 46 ms 100300 KB Output is correct
14 Correct 44 ms 100300 KB Output is correct
15 Correct 43 ms 100392 KB Output is correct
16 Correct 50 ms 100500 KB Output is correct
17 Correct 45 ms 100592 KB Output is correct
18 Correct 43 ms 100292 KB Output is correct
19 Correct 246 ms 101944 KB Output is correct
20 Correct 184 ms 101284 KB Output is correct
21 Correct 649 ms 101548 KB Output is correct
22 Correct 528 ms 101884 KB Output is correct
23 Correct 1302 ms 102464 KB Output is correct
24 Correct 962 ms 102784 KB Output is correct
25 Correct 272 ms 101964 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 100180 KB Output is correct
2 Correct 41 ms 100264 KB Output is correct
3 Correct 41 ms 100268 KB Output is correct
4 Correct 41 ms 100340 KB Output is correct
5 Correct 46 ms 100292 KB Output is correct
6 Correct 45 ms 100284 KB Output is correct
7 Correct 47 ms 100460 KB Output is correct
8 Correct 47 ms 100548 KB Output is correct
9 Correct 40 ms 100184 KB Output is correct
10 Correct 39 ms 100188 KB Output is correct
11 Correct 40 ms 100172 KB Output is correct
12 Correct 40 ms 100296 KB Output is correct
13 Correct 49 ms 100344 KB Output is correct
14 Correct 46 ms 100340 KB Output is correct
15 Correct 44 ms 100300 KB Output is correct
16 Correct 45 ms 100452 KB Output is correct
17 Correct 46 ms 100700 KB Output is correct
18 Correct 41 ms 100248 KB Output is correct
19 Runtime error 124 ms 203920 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 203888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100144 KB Output is correct
2 Runtime error 120 ms 203920 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -