답안 #796729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796729	2023-07-28T16:28:25 Z	GusterGoose27	Passport (JOI23_passport)	C++17	48 / 100	2000 ms	860896 KB

passport

#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--;
		for (int j = l+n; j <= r+n; j++) edges[j].push_back(pii(i+n, 1));
		// 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
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9708 KB	Output is correct
4	Execution timed out	2112 ms	860896 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9720 KB	Output is correct
2	Correct	4 ms	9684 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	4 ms	9684 KB	Output is correct
5	Correct	5 ms	9740 KB	Output is correct
6	Correct	5 ms	9632 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	9724 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	5 ms	9684 KB	Output is correct
13	Correct	5 ms	10324 KB	Output is correct
14	Correct	6 ms	10196 KB	Output is correct
15	Correct	5 ms	9812 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9720 KB	Output is correct
2	Correct	4 ms	9684 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	4 ms	9684 KB	Output is correct
5	Correct	5 ms	9740 KB	Output is correct
6	Correct	5 ms	9632 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	9724 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	5 ms	9684 KB	Output is correct
13	Correct	5 ms	10324 KB	Output is correct
14	Correct	6 ms	10196 KB	Output is correct
15	Correct	5 ms	9812 KB	Output is correct
16	Correct	31 ms	26284 KB	Output is correct
17	Correct	7 ms	10196 KB	Output is correct
18	Correct	64 ms	42336 KB	Output is correct
19	Correct	62 ms	40732 KB	Output is correct
20	Correct	7 ms	10024 KB	Output is correct
21	Correct	13 ms	14548 KB	Output is correct
22	Correct	64 ms	47364 KB	Output is correct
23	Correct	49 ms	36752 KB	Output is correct
24	Correct	50 ms	37520 KB	Output is correct

Subtask #4
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9720 KB	Output is correct
2	Correct	4 ms	9684 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	4 ms	9684 KB	Output is correct
5	Correct	5 ms	9740 KB	Output is correct
6	Correct	5 ms	9632 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	9724 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	5 ms	9684 KB	Output is correct
13	Correct	5 ms	10324 KB	Output is correct
14	Correct	6 ms	10196 KB	Output is correct
15	Correct	5 ms	9812 KB	Output is correct
16	Correct	31 ms	26284 KB	Output is correct
17	Correct	7 ms	10196 KB	Output is correct
18	Correct	64 ms	42336 KB	Output is correct
19	Correct	62 ms	40732 KB	Output is correct
20	Correct	7 ms	10024 KB	Output is correct
21	Correct	13 ms	14548 KB	Output is correct
22	Correct	64 ms	47364 KB	Output is correct
23	Correct	49 ms	36752 KB	Output is correct
24	Correct	50 ms	37520 KB	Output is correct
25	Correct	5 ms	9684 KB	Output is correct
26	Correct	4 ms	9620 KB	Output is correct
27	Correct	34 ms	27440 KB	Output is correct
28	Correct	8 ms	10196 KB	Output is correct
29	Correct	9 ms	10068 KB	Output is correct
30	Correct	13 ms	14292 KB	Output is correct
31	Correct	37 ms	29860 KB	Output is correct

Subtask #5
0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9708 KB	Output is correct
4	Execution timed out	2112 ms	860896 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

답안 #796729

Compilation message

Subtask #1 0 / 6.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 8.0 / 8.0

Subtask #5 0 / 46.0

Subtask #1
0 / 6.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
8.0 / 8.0

Subtask #5
0 / 46.0