oj.uz

Submission #391156

# Submission time Handle Problem Language Result Execution time Memory
391156 2021-04-18T05:59:08 Z palilo Price List (POI13_cen) C++17
70 / 100
 4000 ms 8128 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);
	}

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

	queue<int> q;
	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<bool> neighbor(n);
	vector<int> jump(n, -1);
	jump[k] = 0;

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

		for (const auto& v : adj[u])
			neighbor[v] = true;

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

		for (const auto& v : adj[u])
			neighbor[v] = false;
	}

	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
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 #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
10.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 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1220 KB Output is correct
2 Correct 23 ms 1120 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 10 ms 1356 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 3128 KB Output is correct
2 Correct 738 ms 3144 KB Output is correct
3 Correct 23 ms 2380 KB Output is correct
4 Correct 33 ms 3636 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 5316 KB Output is correct
2 Correct 272 ms 4684 KB Output is correct
3 Correct 96 ms 5268 KB Output is correct
4 Correct 75 ms 6212 KB Output is correct
5 Correct 2738 ms 6532 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1363 ms 6288 KB Output is correct
2 Correct 106 ms 4804 KB Output is correct
3 Correct 89 ms 5312 KB Output is correct
4 Correct 92 ms 6248 KB Output is correct
5 Correct 3677 ms 7292 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 946 ms 7400 KB Output is correct
2 Correct 270 ms 6744 KB Output is correct
3 Correct 82 ms 5928 KB Output is correct
4 Correct 82 ms 6216 KB Output is correct
5 Execution timed out 4072 ms 7544 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 6940 KB Output is correct
2 Correct 275 ms 6952 KB Output is correct
3 Correct 66 ms 6232 KB Output is correct
4 Correct 77 ms 6316 KB Output is correct
5 Execution timed out 4086 ms 8096 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 7260 KB Output is correct
2 Correct 73 ms 7240 KB Output is correct
3 Correct 97 ms 7184 KB Output is correct
4 Correct 73 ms 6340 KB Output is correct
5 Execution timed out 4046 ms 8128 KB Time limit exceeded