oj.uz

답안 #68121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68121 2018-08-16T02:33:12 Z KieranHorgan 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
 1255 ms 100832 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> AdjList[100005];
int visited[100005];
int p[100005];
int ans[100005];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i = 0; i < M; i++) {
		AdjList[R[i][0]].push_back({L[i], R[i][1]});
		AdjList[R[i][1]].push_back({L[i], R[i][0]});
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	for(int i = 0; i < K; i++) {
		q.push({0, P[i]});
		p[P[i]]=1;
	}

	while(!q.empty()) {
		int d = q.top().first;
		int u = q.top().second;
		q.pop();
		if(!p[u] && !visited[u]) {
			visited[u]=1;
			continue;
		}
		if(visited[u] == 2) {
			continue;
		}
		visited[u]=2;
		ans[u] = d;
		for(auto v: AdjList[u])
			if(visited[v.second] != 2)
				q.push({d+v.first, v.second});
	}

	return ans[0];
}

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 5 ms 2856 KB Output is correct
4 Correct 5 ms 2872 KB Output is correct
5 Correct 5 ms 2876 KB Output is correct
6 Correct 5 ms 3024 KB Output is correct
7 Correct 5 ms 3064 KB Output is correct
8 Correct 5 ms 3064 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 5 ms 2856 KB Output is correct
4 Correct 5 ms 2872 KB Output is correct
5 Correct 5 ms 2876 KB Output is correct
6 Correct 5 ms 3024 KB Output is correct
7 Correct 5 ms 3064 KB Output is correct
8 Correct 5 ms 3064 KB Output is correct
9 Correct 8 ms 3260 KB Output is correct
10 Correct 5 ms 3260 KB Output is correct
11 Correct 6 ms 3260 KB Output is correct
12 Correct 11 ms 3732 KB Output is correct
13 Correct 11 ms 3892 KB Output is correct
14 Correct 5 ms 3892 KB Output is correct
15 Correct 8 ms 3892 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 5 ms 2856 KB Output is correct
4 Correct 5 ms 2872 KB Output is correct
5 Correct 5 ms 2876 KB Output is correct
6 Correct 5 ms 3024 KB Output is correct
7 Correct 5 ms 3064 KB Output is correct
8 Correct 5 ms 3064 KB Output is correct
9 Correct 8 ms 3260 KB Output is correct
10 Correct 5 ms 3260 KB Output is correct
11 Correct 6 ms 3260 KB Output is correct
12 Correct 11 ms 3732 KB Output is correct
13 Correct 11 ms 3892 KB Output is correct
14 Correct 5 ms 3892 KB Output is correct
15 Correct 8 ms 3892 KB Output is correct
16 Correct 1212 ms 65232 KB Output is correct
17 Correct 173 ms 65232 KB Output is correct
18 Correct 140 ms 65232 KB Output is correct
19 Correct 1255 ms 90852 KB Output is correct
20 Correct 676 ms 97984 KB Output is correct
21 Correct 68 ms 97984 KB Output is correct
22 Correct 592 ms 100832 KB Output is correct