oj.uz

Submission #577891

# Submission time Handle Problem Language Result Execution time Memory
577891 2022-06-15T11:45:29 Z Markomafko972 Event Hopping (BOI22_events) C++14
0 / 100
 234 ms 23316 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, q, a, b;
pair<int, int> p[100005];
vector< pair<int, int> > v;
set< pair<int, int> > s;
set< pair<int, int> > :: iterator it;
vector<int> sus[100005];
vector<int> roots;
int dub[100005];
int prt[20][100005];

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	if (p1.X == p2.X) {
		if (p[p1.Y].X == p1.X) return true;
		else return false;
	}
	return p1.X < p2.X;
}

void rek(int x, int d) {
	dub[x] = d;
	
	for (int i = 0; i < sus[x].size(); i++) {
		prt[0][sus[x][i]] = x;
		rek(sus[x][i], d+1);
	}
}

int main () {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> p[i].X >> p[i].Y;
		v.push_back({p[i].X, i});
		v.push_back({p[i].Y, i});
	}
	
	sort(v.begin(), v.end(), cmp);
	
	for (int i = 0; i < v.size(); i++) {
		int ps = i;
		while (ps < v.size() && v[i].X == v[ps].X) ps++;
		for (int j = i; j < ps; j++) {
			if (v[j].X == p[v[j].Y].X) {
				s.insert({p[v[j].Y].Y, v[j].Y});
				//cout << "dodaj " << p[v[i].Y].Y << " " << v[i].Y << endl;
			}
			else {
				it = s.end();
				it--;
				
				//cout << v[i].Y+1 << " -> " << (it -> second)+1 << endl;
				if (v[j].Y != (it -> second)) sus[(it -> second)+1].push_back(v[j].Y+1);
				else roots.push_back(v[j].Y+1);
				//cout << "makni " << v[i].X << " " << v[i].Y << endl;
			}
		}
		
		for (int j = i; j < ps; j++) {
			if (v[j].X != p[v[j].Y].X) s.erase(v[j]);
		}
		i = ps-1;
	}
	
	for (int i = 0; i < roots.size(); i++) {
		rek(roots[i], 1);
	}
	
	for (int i = 1; i < 20; i++) {
		for (int j = 1; j <= n; j++) {
			prt[i][j] = prt[i-1][prt[i-1][j]];
		}
	}
	
	for (int i = 0; i < q; i++) {
		cin >> a >> b;
		int mini = dub[a]-dub[b];
		for (int j = 19; j >= 0; j--) {
			if (dub[prt[j][a]] >= dub[b]) a = prt[j][a];
		}
		
		if (a == b) cout << mini << "\n";
		else cout << "impossible\n";
	}
	
	return 0;
}

Compilation message

events.cpp: In function 'void rek(int, int)':
events.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < sus[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
events.cpp: In function 'int main()':
events.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
events.cpp:49:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while (ps < v.size() && v[i].X == v[ps].X) ps++;
      |          ~~~^~~~~~~~~~
events.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < roots.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 113 ms 23196 KB Output is correct
3 Correct 144 ms 23180 KB Output is correct
4 Correct 227 ms 23316 KB Output is correct
5 Correct 161 ms 22308 KB Output is correct
6 Correct 132 ms 21384 KB Output is correct
7 Incorrect 150 ms 21216 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Incorrect 3 ms 2772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Incorrect 3 ms 2772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Incorrect 3 ms 2772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 23208 KB Output is correct
2 Correct 167 ms 23164 KB Output is correct
3 Correct 234 ms 23168 KB Output is correct
4 Correct 117 ms 14788 KB Output is correct
5 Correct 223 ms 20384 KB Output is correct
6 Incorrect 216 ms 17564 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 113 ms 23196 KB Output is correct
3 Correct 144 ms 23180 KB Output is correct
4 Correct 227 ms 23316 KB Output is correct
5 Correct 161 ms 22308 KB Output is correct
6 Correct 132 ms 21384 KB Output is correct
7 Incorrect 150 ms 21216 KB Output isn't correct
8 Halted 0 ms 0 KB -