답안 #607687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
607687	2022-07-27T00:42:37 Z	Temmie	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	479 ms	87620 KB

crocodile

#include <bits/stdc++.h>

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	std::vector <std::vector <std::pair <int, int>>> g(n);
	for (int i = 0; i < m; i++) {
		g[r[i][0]].emplace_back(r[i][1], l[i]);
		g[r[i][1]].emplace_back(r[i][0], l[i]);
	}
	std::vector <int> cnt(n, 0);
	std::priority_queue <std::pair <long long, int>> pq;
	for (int i = 0; i < k; i++) {
		cnt[p[i]] = 1;
		pq.push({ 0, p[i] });
	}
	while (pq.size()) {
		long long w = -pq.top().first;
		int v = pq.top().second;
		pq.pop();
		if (cnt[v] >= 2) {
			continue;
		}
		cnt[v]++;
		if (cnt[v] == 1) {
			continue;
		}
		assert(cnt[v] == 2);
		if (!v) {
			return w;
		}
		for (auto q : g[v]) {
			pq.push({ -w - q.second, q.first });
		}
	}
	assert(false);
	return 0;
}

Subtask #1

46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	724 KB	Output is correct
10	Correct	1 ms	308 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	5 ms	1368 KB	Output is correct
13	Correct	3 ms	1460 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	724 KB	Output is correct
10	Correct	1 ms	308 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	5 ms	1368 KB	Output is correct
13	Correct	3 ms	1460 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	440 ms	87620 KB	Output is correct
17	Correct	79 ms	13308 KB	Output is correct
18	Correct	79 ms	14844 KB	Output is correct
19	Correct	448 ms	75048 KB	Output is correct
20	Correct	291 ms	80200 KB	Output is correct
21	Correct	39 ms	5836 KB	Output is correct
22	Correct	479 ms	45400 KB	Output is correct