답안 #796732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
796732 2023-07-28T16:31:24 Z GusterGoose27 Passport (JOI23_passport) C++17
22 / 100
685 ms 76564 KB
#include <bits/stdc++.h>

using namespace std;

const int MAXN = (1<<18)+5;
const int inf = 1e9+7;

typedef pair<int, int> pii;

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

vector<pii> edges[2*MAXN];

void build() {
	for (int i = 1; i < m; 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*m; 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;
	m = 1;
	for (; m < n; m *= 2);
	build();
	fill(dist[0], dist[0]+2*m, inf);
	fill(dist[1], dist[1]+2*m, inf);
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l >> r;
		l--; r--;
		// for (int j = l+n; j <= r+n; j++) edges[j].push_back(pii(i+n, 1));
		assign(i+m, l+m, r+m+1);
		if (l == 0) dist[0][i+m] = 0;
		if (r == n-1) dist[1][i+m] = 0;
	}
	dijkstra(dist[0]);
	dijkstra(dist[1]);
	for (int i = 0; i < 2*m; 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 += m-1;
		cout << ((sumdist[s] < inf) ? sumdist[s]+1 : -1) << '\n';
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12628 KB Output is correct
2 Correct 6 ms 12628 KB Output is correct
3 Correct 7 ms 12628 KB Output is correct
4 Correct 685 ms 76564 KB Output is correct
5 Correct 451 ms 53672 KB Output is correct
6 Correct 374 ms 50272 KB Output is correct
7 Correct 284 ms 60260 KB Output is correct
8 Correct 243 ms 62300 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12628 KB Output is correct
2 Correct 6 ms 12540 KB Output is correct
3 Correct 6 ms 12628 KB Output is correct
4 Correct 6 ms 12628 KB Output is correct
5 Correct 6 ms 12628 KB Output is correct
6 Correct 6 ms 12628 KB Output is correct
7 Correct 8 ms 12628 KB Output is correct
8 Correct 8 ms 12772 KB Output is correct
9 Correct 6 ms 12628 KB Output is correct
10 Correct 6 ms 12628 KB Output is correct
11 Correct 7 ms 12628 KB Output is correct
12 Correct 7 ms 12628 KB Output is correct
13 Correct 6 ms 12756 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 6 ms 12628 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12628 KB Output is correct
2 Correct 6 ms 12540 KB Output is correct
3 Correct 6 ms 12628 KB Output is correct
4 Correct 6 ms 12628 KB Output is correct
5 Correct 6 ms 12628 KB Output is correct
6 Correct 6 ms 12628 KB Output is correct
7 Correct 8 ms 12628 KB Output is correct
8 Correct 8 ms 12772 KB Output is correct
9 Correct 6 ms 12628 KB Output is correct
10 Correct 6 ms 12628 KB Output is correct
11 Correct 7 ms 12628 KB Output is correct
12 Correct 7 ms 12628 KB Output is correct
13 Correct 6 ms 12756 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 6 ms 12628 KB Output is correct
16 Incorrect 11 ms 13384 KB Output isn't correct
17 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12628 KB Output is correct
2 Correct 6 ms 12540 KB Output is correct
3 Correct 6 ms 12628 KB Output is correct
4 Correct 6 ms 12628 KB Output is correct
5 Correct 6 ms 12628 KB Output is correct
6 Correct 6 ms 12628 KB Output is correct
7 Correct 8 ms 12628 KB Output is correct
8 Correct 8 ms 12772 KB Output is correct
9 Correct 6 ms 12628 KB Output is correct
10 Correct 6 ms 12628 KB Output is correct
11 Correct 7 ms 12628 KB Output is correct
12 Correct 7 ms 12628 KB Output is correct
13 Correct 6 ms 12756 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 6 ms 12628 KB Output is correct
16 Incorrect 11 ms 13384 KB Output isn't correct
17 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12628 KB Output is correct
2 Correct 6 ms 12628 KB Output is correct
3 Correct 7 ms 12628 KB Output is correct
4 Correct 685 ms 76564 KB Output is correct
5 Correct 451 ms 53672 KB Output is correct
6 Correct 374 ms 50272 KB Output is correct
7 Correct 284 ms 60260 KB Output is correct
8 Correct 243 ms 62300 KB Output is correct
9 Correct 6 ms 12628 KB Output is correct
10 Correct 6 ms 12540 KB Output is correct
11 Correct 6 ms 12628 KB Output is correct
12 Correct 6 ms 12628 KB Output is correct
13 Correct 6 ms 12628 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 8 ms 12628 KB Output is correct
16 Correct 8 ms 12772 KB Output is correct
17 Correct 6 ms 12628 KB Output is correct
18 Correct 6 ms 12628 KB Output is correct
19 Correct 7 ms 12628 KB Output is correct
20 Correct 7 ms 12628 KB Output is correct
21 Correct 6 ms 12756 KB Output is correct
22 Correct 6 ms 12628 KB Output is correct
23 Correct 6 ms 12628 KB Output is correct
24 Incorrect 11 ms 13384 KB Output isn't correct
25 Halted 0 ms 0 KB -