oj.uz

답안 #226162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
226162 2020-04-22T17:10:30 Z dolphingarlic Price List (POI13_cen) C++14
100 / 100
 285 ms 31548 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

set<int> graph[100001], second_visit[100001];
int visited[100001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, k, a, b;
	cin >> n >> m >> k >> a >> b;
	FOR(i, 0, m) {
		int u, v;
		cin >> u >> v;
		graph[u].insert(v);
		graph[v].insert(u);
		second_visit[u].insert(v);
		second_visit[v].insert(u);
	}

	priority_queue<pair<int, int>> pq;
	pq.push({-1, k});
	while (pq.size()) {
		pair<int, int> curr = pq.top();
		pq.pop();
		if (!visited[curr.second]) {
			visited[curr.second] = -curr.first;
			for (int i : graph[curr.second]) {
				pq.push({curr.first - a, i});

				vector<int> to_remove;
				for (int j : second_visit[i]) {
					if (graph[curr.second].find(j) == graph[curr.second].end()) {
						to_remove.push_back(j);
						pq.push({curr.first - b, j});
					}
				}
				for (int j : to_remove) second_visit[i].erase(j);
			}
		}
	}

	FOR(i, 1, n + 1) cout << visited[i] - 1 << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 10 ms 9820 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 13 ms 9856 KB Output is correct
4 Correct 11 ms 9920 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 12416 KB Output is correct
2 Correct 25 ms 12416 KB Output is correct
3 Correct 36 ms 13184 KB Output is correct
4 Correct 32 ms 13312 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 18676 KB Output is correct
2 Correct 74 ms 18676 KB Output is correct
3 Correct 101 ms 18120 KB Output is correct
4 Correct 121 ms 21240 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 24728 KB Output is correct
2 Correct 108 ms 22900 KB Output is correct
3 Correct 223 ms 27908 KB Output is correct
4 Correct 217 ms 29304 KB Output is correct
5 Correct 152 ms 25820 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 27700 KB Output is correct
2 Correct 105 ms 23292 KB Output is correct
3 Correct 272 ms 29768 KB Output is correct
4 Correct 228 ms 29472 KB Output is correct
5 Correct 173 ms 27848 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 30572 KB Output is correct
2 Correct 151 ms 28528 KB Output is correct
3 Correct 285 ms 29824 KB Output is correct
4 Correct 233 ms 29352 KB Output is correct
5 Correct 189 ms 29636 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 29172 KB Output is correct
2 Correct 153 ms 29168 KB Output is correct
3 Correct 251 ms 29944 KB Output is correct
4 Correct 202 ms 29432 KB Output is correct
5 Correct 217 ms 31548 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 30072 KB Output is correct
2 Correct 155 ms 29820 KB Output is correct
3 Correct 252 ms 30072 KB Output is correct
4 Correct 201 ms 29432 KB Output is correct
5 Correct 217 ms 31544 KB Output is correct