oj.uz

Submission #571446

# Submission time Handle Problem Language Result Execution time Memory
571446 2022-06-02T09:02:44 Z choigameautohackrb Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 55756 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll N = 1e6 + 5;
const ll inf = 1e9;

ll n, m, k, qq, d[N];
vector <pair<ll, ll>> g[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (ll i = 1; i <= m; ++ i) {
		ll u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for (int i = 1; i <= n; ++ i) d[i] = inf;
	cin >> k;
	queue <int> Que;
	for (int i = 1; i <= k; ++ i) {
		ll x; cin >> x;
		d[x] = 0;
		Que.push(x);
	}
	while (Que.size()) {
		ll v = Que.front();
		Que.pop();
		for (auto [to, w] : g[v]) {
			if (d[to] > d[v] + w) {
		    	d[to] = d[v] + w;
				Que.push(to);
			}
		}
	}
	cin >> qq;
	while (qq --) {
		ll a, b;
		cin >> a >> b;
		vector <ll> res(n + 5, 0);
		Que.push(a);
		res[a] = d[a];
		while (Que.size()) {
			ll v = Que.front();
			Que.pop();
			for (auto [to, w] : g[v]) {
				if (res[to] < min(res[v], d[to])) {
					res[to] = min(res[v], d[to]);
					Que.push(to);
				}
			}
		}
		cout << res[b] << '\n';
	}
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 24 ms 23884 KB Output is correct
3 Correct 25 ms 23892 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 24 ms 23892 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 36 ms 23892 KB Output is correct
10 Correct 15 ms 23892 KB Output is correct
11 Correct 33 ms 23892 KB Output is correct
12 Correct 25 ms 23892 KB Output is correct
13 Correct 20 ms 23892 KB Output is correct
14 Correct 36 ms 23880 KB Output is correct
15 Correct 35 ms 23892 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 24 ms 23884 KB Output is correct
3 Correct 25 ms 23892 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 24 ms 23892 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 36 ms 23892 KB Output is correct
10 Correct 15 ms 23892 KB Output is correct
11 Correct 33 ms 23892 KB Output is correct
12 Correct 25 ms 23892 KB Output is correct
13 Correct 20 ms 23892 KB Output is correct
14 Correct 36 ms 23880 KB Output is correct
15 Correct 35 ms 23892 KB Output is correct
16 Execution timed out 4072 ms 31824 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23784 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 12 ms 23820 KB Output is correct
4 Correct 13 ms 23788 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23760 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 14 ms 23728 KB Output is correct
9 Correct 12 ms 23768 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 38364 KB Output is correct
2 Correct 439 ms 55528 KB Output is correct
3 Correct 381 ms 55756 KB Output is correct
4 Correct 55 ms 31344 KB Output is correct
5 Correct 356 ms 55484 KB Output is correct
6 Correct 390 ms 55480 KB Output is correct
7 Correct 376 ms 55524 KB Output is correct
8 Correct 388 ms 55428 KB Output is correct
9 Correct 404 ms 55612 KB Output is correct
10 Correct 405 ms 55560 KB Output is correct
11 Correct 385 ms 55376 KB Output is correct
12 Correct 377 ms 54348 KB Output is correct
13 Correct 381 ms 54272 KB Output is correct
14 Correct 370 ms 54256 KB Output is correct
15 Correct 362 ms 54272 KB Output is correct
16 Correct 398 ms 54644 KB Output is correct
17 Correct 398 ms 54828 KB Output is correct
18 Correct 437 ms 54640 KB Output is correct
19 Correct 55 ms 31436 KB Output is correct
20 Correct 362 ms 54372 KB Output is correct
21 Correct 276 ms 54104 KB Output is correct
22 Correct 50 ms 31852 KB Output is correct
23 Correct 60 ms 31712 KB Output is correct
24 Correct 52 ms 31800 KB Output is correct
25 Correct 48 ms 31780 KB Output is correct
26 Correct 57 ms 31864 KB Output is correct
27 Correct 69 ms 31352 KB Output is correct
28 Correct 51 ms 31828 KB Output is correct
29 Correct 54 ms 31452 KB Output is correct
30 Correct 51 ms 31808 KB Output is correct
31 Correct 56 ms 31436 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 24 ms 23884 KB Output is correct
3 Correct 25 ms 23892 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 24 ms 23892 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 36 ms 23892 KB Output is correct
10 Correct 15 ms 23892 KB Output is correct
11 Correct 33 ms 23892 KB Output is correct
12 Correct 25 ms 23892 KB Output is correct
13 Correct 20 ms 23892 KB Output is correct
14 Correct 36 ms 23880 KB Output is correct
15 Correct 35 ms 23892 KB Output is correct
16 Execution timed out 4072 ms 31824 KB Time limit exceeded
17 Halted 0 ms 0 KB -