oj.uz

Submission #391152

# Submission time Handle Problem Language Result Execution time Memory
391152 2021-04-18T05:50:03 Z palilo Price List (POI13_cen) C++17
10 / 100
 88 ms 8516 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
#endif
	int n, m, k, a, b;
	cin >> n >> m >> k >> a >> b, --k;

	vector<vector<int>> adj(n);
	for (int u, v; m--;) {
		cin >> u >> v, --u, --v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}

	for (auto& vt : adj)
		sort(vt.begin(), vt.end());

	queue<int> q;

	vector<int> step(n, -1);
	step[k] = 0;

	q.emplace(k);
	while (!q.empty()) {
		const auto u = q.front();
		q.pop();

		for (const auto& v : adj[u])
			if (step[v] == -1) {
				step[v] = step[u] + 1;
				q.emplace(v);
			}
	}

	vector<int> jump(n, -1);
	jump[k] = 0;

	q.emplace(k);
	while (!q.empty()) {
		const auto u = q.front();
		q.pop();

		for (const auto& via : adj[u])
			adj[via].erase(remove_if(adj[via].begin(), adj[via].end(), [&](auto& v) {
							   if (~jump[v] || binary_search(adj[u].begin(), adj[u].end(), v)) return false;
							   jump[v] = jump[u] + 1;
							   q.emplace(v);
							   return true;
						   }),
						   adj[via].end());
	}

	for (int i = 0; i < n; ++i)
		cout << min({step[i] * a,
					 (step[i] & 1) * a + (step[i] >> 1) * b,
					 ~jump[i] ? jump[i] * b : INT_MAX})
			 << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1228 KB Output is correct
2 Correct 7 ms 1296 KB Output is correct
3 Incorrect 10 ms 1356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3660 KB Output is correct
2 Correct 23 ms 3648 KB Output is correct
3 Incorrect 25 ms 2792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6080 KB Output is correct
2 Correct 46 ms 5384 KB Output is correct
3 Incorrect 69 ms 6296 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7208 KB Output is correct
2 Correct 39 ms 5584 KB Output is correct
3 Incorrect 64 ms 6500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8516 KB Output is correct
2 Correct 66 ms 7752 KB Output is correct
3 Incorrect 88 ms 6980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 7972 KB Output is correct
2 Correct 57 ms 8004 KB Output is correct
3 Incorrect 68 ms 7384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8472 KB Output is correct
2 Correct 66 ms 8380 KB Output is correct
3 Incorrect 80 ms 8352 KB Output isn't correct
4 Halted 0 ms 0 KB -