Submission #391157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
391157	2021-04-18T06:08:20 Z	palilo	Price List (POI13_cen)	C++17	100 / 100	95 ms	13160 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<vector<int>> vtx = adj;
	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])
			vtx[via].erase(remove_if(vtx[via].begin(), vtx[via].end(), [&](auto& v) {
							   if (neighbor[v] || ~jump[v]) return false;
							   jump[v] = jump[u] + 1;
							   q.emplace(v);
							   return true;
						   }),
						   vtx[via].end());

		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	0 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	7 ms	1824 KB	Output is correct
2	Correct	7 ms	1740 KB	Output is correct
3	Correct	11 ms	1740 KB	Output is correct
4	Correct	10 ms	1744 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	5400 KB	Output is correct
2	Correct	33 ms	5444 KB	Output is correct
3	Correct	27 ms	3932 KB	Output is correct
4	Correct	35 ms	5192 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	9252 KB	Output is correct
2	Correct	44 ms	8108 KB	Output is correct
3	Correct	69 ms	9184 KB	Output is correct
4	Correct	71 ms	8772 KB	Output is correct
5	Correct	54 ms	9792 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	11084 KB	Output is correct
2	Correct	47 ms	8396 KB	Output is correct
3	Correct	78 ms	9044 KB	Output is correct
4	Correct	69 ms	8712 KB	Output is correct
5	Correct	61 ms	11200 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	12944 KB	Output is correct
2	Correct	79 ms	11720 KB	Output is correct
3	Correct	82 ms	10436 KB	Output is correct
4	Correct	69 ms	8716 KB	Output is correct
5	Correct	71 ms	12224 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	12076 KB	Output is correct
2	Correct	79 ms	12192 KB	Output is correct
3	Correct	89 ms	10824 KB	Output is correct
4	Correct	68 ms	8824 KB	Output is correct
5	Correct	84 ms	13160 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	12740 KB	Output is correct
2	Correct	83 ms	12620 KB	Output is correct
3	Correct	95 ms	12656 KB	Output is correct
4	Correct	67 ms	8772 KB	Output is correct
5	Correct	74 ms	13120 KB	Output is correct

Submission #391157

Compilation message