Submission #583647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583647	2022-06-25T21:12:54 Z	tutis	Event Hopping (BOI22_events)	C++17	0 / 100	321 ms	524288 KB

events

/*input
8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, Q;
	cin >> N >> Q;
	pair<pair<int, int>, int>A[N];
	for (int i = 0; i < N; i++)
	{
		cin >> A[i].first.second >> A[i].first.first;
		A[i].second = i;
	}
	sort(A, A + N);
	int p[N];
	for (int i = 0; i < N; i++)
		p[A[i].second] = i;
	int S[N], E[N];
	for (int i = 0; i < N; i++)
	{
		S[i] = A[i].first.second;
		E[i] = A[i].first.first;
	}
	for (int i = 0; i < N; i++)
	{
		//S[i] = upper_bound(E, E + N, S[i]) - E;
	}
	int D[N][N];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			D[i][j] = N + 10;
	for (int i = N - 1; i >= 0; i--)
	{
		D[i][i] = 0;
		for (int j = i + 1; j < N; j++)
		{
			if (S[j] <= E[i])
				D[i][j] = 1;
			else
			{
				for (int k = i + 1; k < j; k++)
					D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
			}
		}
	}
	while (Q--)
	{
		int s, t;
		cin >> s >> t;
		s = p[s - 1];
		t = p[t - 1];
		int k = D[s][t];
		if (k > N)
			cout << "impossible\n";
		else
			cout << k << "\n";
	}
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	222 ms	524288 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	321 ms	4240 KB	Output is correct
4	Correct	261 ms	4244 KB	Output is correct
5	Correct	256 ms	4228 KB	Output is correct
6	Correct	183 ms	4236 KB	Output is correct
7	Correct	129 ms	4180 KB	Output is correct
8	Correct	3 ms	4180 KB	Output is correct
9	Incorrect	3 ms	4180 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	321 ms	4240 KB	Output is correct
4	Correct	261 ms	4244 KB	Output is correct
5	Correct	256 ms	4228 KB	Output is correct
6	Correct	183 ms	4236 KB	Output is correct
7	Correct	129 ms	4180 KB	Output is correct
8	Correct	3 ms	4180 KB	Output is correct
9	Incorrect	3 ms	4180 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	321 ms	4240 KB	Output is correct
4	Correct	261 ms	4244 KB	Output is correct
5	Correct	256 ms	4228 KB	Output is correct
6	Correct	183 ms	4236 KB	Output is correct
7	Correct	129 ms	4180 KB	Output is correct
8	Correct	3 ms	4180 KB	Output is correct
9	Incorrect	3 ms	4180 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	223 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	222 ms	524288 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-