oj.uz

Submission #796726

# Submission time Handle Problem Language Result Execution time Memory
796726 2023-07-28T16:23:48 Z GusterGoose27 Passport (JOI23_passport) C++17
22 / 100
 600 ms 65088 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
const int inf = 1e9+7;

typedef pair<int, int> pii;

int dist[2][2*MAXN];
int sumdist[2*MAXN];
int n;

vector<pii> edges[2*MAXN];

void build() {
	for (int i = 1; i < n; i++) {
		edges[2*i].push_back(pii(i, 0));
		edges[2*i+1].push_back(pii(i, 0));
	}
}

void assign(int i, int l, int r) {
	for (; r > l; l /= 2, r /= 2) {
		if (l & 1) edges[l++].push_back(pii(i, 1));
		if (r & 1) edges[--r].push_back(pii(i, 1));
	}
}

void dijkstra(int curdist[]) {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 0; i < 2*n; i++)
		pq.push(pii(curdist[i], i));
	while (!pq.empty()) {
		pii tp = pq.top();
		pq.pop();
		int cur = tp.second;
		if (tp.first > curdist[cur]) continue;
		for (pii p: edges[cur]) {
			int nxtdist = tp.first+p.second;
			if (nxtdist < curdist[p.first]) {
				curdist[p.first] = nxtdist;
				pq.push(pii(nxtdist, p.first));
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	build();
	fill(dist[0], dist[0]+2*n, inf);
	fill(dist[1], dist[1]+2*n, inf);
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l >> r;
		l--; r--;
		assign(i+n, l+n, r+n+1);
		if (l == 0) dist[0][i+n] = 0;
		if (r == n-1) dist[1][i+n] = 0;
	}
	dijkstra(dist[0]);
	dijkstra(dist[1]);
	for (int i = 0; i < 2*n; i++) {
		sumdist[i] = min(inf, dist[0][i]+dist[1][i]);
	}
	dijkstra(sumdist);
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int s; cin >> s; s += n-1;
		cout << ((sumdist[s] < inf) ? sumdist[s]+1 : -1) << '\n';
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 600 ms 65088 KB Output is correct
5 Correct 354 ms 44572 KB Output is correct
6 Correct 294 ms 41312 KB Output is correct
7 Correct 243 ms 58292 KB Output is correct
8 Correct 190 ms 55340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9728 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9724 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9796 KB Output is correct
13 Correct 6 ms 9720 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9728 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9724 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9796 KB Output is correct
13 Correct 6 ms 9720 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Incorrect 10 ms 10328 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9728 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9724 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9796 KB Output is correct
13 Correct 6 ms 9720 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Incorrect 10 ms 10328 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 600 ms 65088 KB Output is correct
5 Correct 354 ms 44572 KB Output is correct
6 Correct 294 ms 41312 KB Output is correct
7 Correct 243 ms 58292 KB Output is correct
8 Correct 190 ms 55340 KB Output is correct
9 Correct 5 ms 9728 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 6 ms 9728 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9724 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9796 KB Output is correct
21 Correct 6 ms 9720 KB Output is correct
22 Correct 5 ms 9684 KB Output is correct
23 Correct 5 ms 9684 KB Output is correct
24 Incorrect 10 ms 10328 KB Output isn't correct
25 Halted 0 ms 0 KB -