답안 #756583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756583	2023-06-12T00:53:54 Z	pavement	악어의 지하 도시 (IOI11_crocodile)	C++17	89 / 100	466 ms	45020 KB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back
using ii = pair<int, int>;

int fd[100005], sd[100005];
vector<ii> adj[100005];
priority_queue<ii, vector<ii>, greater<ii> > pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i = 0; i < M; i++) {
		adj[R[i][0]].eb(R[i][1], L[i]);
		adj[R[i][1]].eb(R[i][0], L[i]);
	}
	for (int i = 0; i < N; i++) {
		fd[i] = sd[i] = (int)2e9;
	}
	for (int i = 0; i < K; i++) {
		fd[P[i]] = sd[P[i]] = 0;
		pq.emplace(0, P[i]);
	}
	while (!pq.empty()) {
		auto [d, v] = pq.top();
		pq.pop();
		if (sd[v] != d) continue;
		for (auto [u, w] : adj[v]) {
			int c = d + w;
			if (c < sd[u]) {
				sd[u] = c;
				if (sd[u] < fd[u]) swap(fd[u], sd[u]);
				if (sd[u] != (int)2e9) pq.emplace(sd[u], u);
			}
		}
	}
	return sd[0];
}

Subtask #1

46.0 / 46.0

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

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	3 ms	2644 KB	Output is correct
5	Correct	2 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2720 KB	Output is correct
9	Correct	3 ms	2900 KB	Output is correct
10	Correct	2 ms	2644 KB	Output is correct
11	Correct	4 ms	2772 KB	Output is correct
12	Correct	5 ms	3028 KB	Output is correct
13	Correct	5 ms	3028 KB	Output is correct
14	Correct	2 ms	2644 KB	Output is correct
15	Correct	2 ms	2644 KB	Output is correct

Subtask #3

0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	3 ms	2644 KB	Output is correct
5	Correct	2 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2720 KB	Output is correct
9	Correct	3 ms	2900 KB	Output is correct
10	Correct	2 ms	2644 KB	Output is correct
11	Correct	4 ms	2772 KB	Output is correct
12	Correct	5 ms	3028 KB	Output is correct
13	Correct	5 ms	3028 KB	Output is correct
14	Correct	2 ms	2644 KB	Output is correct
15	Correct	2 ms	2644 KB	Output is correct
16	Correct	393 ms	41152 KB	Output is correct
17	Correct	78 ms	10472 KB	Output is correct
18	Correct	84 ms	11708 KB	Output is correct
19	Correct	466 ms	45020 KB	Output is correct
20	Correct	253 ms	36540 KB	Output is correct
21	Correct	32 ms	6200 KB	Output is correct
22	Incorrect	269 ms	31752 KB	Output isn't correct
23	Halted	0 ms	0 KB	-