oj.uz

Submission #41165

# Submission time Handle Problem Language Result Execution time Memory
41165 2018-02-13T07:53:03 Z aome Evacuation plan (IZhO18_plan) C++14
100 / 100
 1605 ms 33108 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

typedef pair<int, int> ii;

int n, m, k, q;
int a[N], dis[N];
int x[N], y[N];
int l[N], r[N];
int par[N];
vector<ii> G[N];
vector<ii> vec;
vector<int> queries[N];

int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }

void join(int u, int v) { par[find(u)] = find(v); }

void dijkstra() {
	for (int i = 1; i <= n; ++i) dis[i] = 1e9;
	priority_queue< ii, vector<ii>, greater<ii> > pq;
	for (int i = 1; i <= k; ++i) {
		pq.push(ii(0, a[i])), dis[a[i]] = 0;
	}
	while (pq.size()) {
		ii u = pq.top(); pq.pop();
		if (u.first != dis[u.second]) continue;
		for (auto v : G[u.second]) {
			v.first += u.first;
			if (v.first < dis[v.second]) {
				dis[v.second] = v.first, pq.push(v);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		G[u].push_back(ii(w, v)), G[v].push_back(ii(w, u));
	}
	cin >> k;
	for (int i = 1; i <= k; ++i) cin >> a[i];
	dijkstra();
	vec.push_back(ii(1e9, 0));
	for (int i = 1; i <= n; ++i) vec.push_back(ii(dis[i], i));
	sort(vec.begin(), vec.end(), greater<ii>());
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		cin >> x[i] >> y[i];
		l[i] = 1, r[i] = n;
	}
	while (1) {
		bool found = 0;
		for (int i = 1; i <= q; ++i) found |= l[i] < r[i];
		if (!found) break;
		for (int i = 1; i <= n; ++i) par[i] = i;
		for (int i = 1; i <= n; ++i) queries[i].clear();
		for (int i = 1; i <= q; ++i) {
			queries[(l[i] + r[i]) / 2].push_back(i);
		}
		for (int i = 1; i <= n; ++i) {
			for (auto j : G[vec[i].second]) {
				if (dis[j.second] >= dis[vec[i].second]) join(vec[i].second, j.second);
			}
			for (auto j : queries[i]) {
				if (find(x[j]) == find(y[j])) r[j] = (l[j] + r[j]) / 2;
				else l[j] = (l[j] + r[j]) / 2 + 1;
			}
		}
	}
	for (int i = 1; i <= q; ++i) cout << vec[l[i]].first << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Correct 7 ms 5112 KB Output is correct
13 Correct 8 ms 5240 KB Output is correct
14 Correct 7 ms 5240 KB Output is correct
15 Correct 8 ms 5216 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Correct 7 ms 5112 KB Output is correct
13 Correct 8 ms 5240 KB Output is correct
14 Correct 7 ms 5240 KB Output is correct
15 Correct 8 ms 5216 KB Output is correct
16 Correct 556 ms 21380 KB Output is correct
17 Correct 1539 ms 31436 KB Output is correct
18 Correct 75 ms 7496 KB Output is correct
19 Correct 230 ms 20840 KB Output is correct
20 Correct 1494 ms 31376 KB Output is correct
21 Correct 916 ms 24256 KB Output is correct
22 Correct 495 ms 22268 KB Output is correct
23 Correct 1489 ms 31344 KB Output is correct
24 Correct 1555 ms 31368 KB Output is correct
25 Correct 1508 ms 31244 KB Output is correct
26 Correct 296 ms 20744 KB Output is correct
27 Correct 308 ms 21212 KB Output is correct
28 Correct 249 ms 20952 KB Output is correct
29 Correct 244 ms 20572 KB Output is correct
30 Correct 223 ms 20540 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5092 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5044 KB Output is correct
5 Correct 6 ms 4988 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 5 ms 5112 KB Output is correct
10 Correct 6 ms 4988 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 13504 KB Output is correct
2 Correct 1174 ms 21696 KB Output is correct
3 Correct 1258 ms 21692 KB Output is correct
4 Correct 260 ms 9924 KB Output is correct
5 Correct 1225 ms 21692 KB Output is correct
6 Correct 1225 ms 21736 KB Output is correct
7 Correct 1226 ms 21628 KB Output is correct
8 Correct 1253 ms 21672 KB Output is correct
9 Correct 1240 ms 21692 KB Output is correct
10 Correct 1212 ms 21584 KB Output is correct
11 Correct 1238 ms 21604 KB Output is correct
12 Correct 1263 ms 21728 KB Output is correct
13 Correct 1237 ms 21584 KB Output is correct
14 Correct 1254 ms 21820 KB Output is correct
15 Correct 1226 ms 21668 KB Output is correct
16 Correct 1278 ms 21704 KB Output is correct
17 Correct 1184 ms 21800 KB Output is correct
18 Correct 1207 ms 21908 KB Output is correct
19 Correct 200 ms 9836 KB Output is correct
20 Correct 1180 ms 21728 KB Output is correct
21 Correct 1284 ms 22008 KB Output is correct
22 Correct 172 ms 13180 KB Output is correct
23 Correct 202 ms 10348 KB Output is correct
24 Correct 149 ms 12256 KB Output is correct
25 Correct 159 ms 12988 KB Output is correct
26 Correct 266 ms 10428 KB Output is correct
27 Correct 184 ms 9832 KB Output is correct
28 Correct 159 ms 12260 KB Output is correct
29 Correct 239 ms 9964 KB Output is correct
30 Correct 145 ms 12244 KB Output is correct
31 Correct 192 ms 9832 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Correct 7 ms 5112 KB Output is correct
13 Correct 8 ms 5240 KB Output is correct
14 Correct 7 ms 5240 KB Output is correct
15 Correct 8 ms 5216 KB Output is correct
16 Correct 556 ms 21380 KB Output is correct
17 Correct 1539 ms 31436 KB Output is correct
18 Correct 75 ms 7496 KB Output is correct
19 Correct 230 ms 20840 KB Output is correct
20 Correct 1494 ms 31376 KB Output is correct
21 Correct 916 ms 24256 KB Output is correct
22 Correct 495 ms 22268 KB Output is correct
23 Correct 1489 ms 31344 KB Output is correct
24 Correct 1555 ms 31368 KB Output is correct
25 Correct 1508 ms 31244 KB Output is correct
26 Correct 296 ms 20744 KB Output is correct
27 Correct 308 ms 21212 KB Output is correct
28 Correct 249 ms 20952 KB Output is correct
29 Correct 244 ms 20572 KB Output is correct
30 Correct 223 ms 20540 KB Output is correct
31 Correct 6 ms 5092 KB Output is correct
32 Correct 6 ms 4984 KB Output is correct
33 Correct 6 ms 5112 KB Output is correct
34 Correct 6 ms 5044 KB Output is correct
35 Correct 6 ms 4988 KB Output is correct
36 Correct 6 ms 5112 KB Output is correct
37 Correct 6 ms 4984 KB Output is correct
38 Correct 6 ms 4984 KB Output is correct
39 Correct 5 ms 5112 KB Output is correct
40 Correct 6 ms 4988 KB Output is correct
41 Correct 628 ms 13504 KB Output is correct
42 Correct 1174 ms 21696 KB Output is correct
43 Correct 1258 ms 21692 KB Output is correct
44 Correct 260 ms 9924 KB Output is correct
45 Correct 1225 ms 21692 KB Output is correct
46 Correct 1225 ms 21736 KB Output is correct
47 Correct 1226 ms 21628 KB Output is correct
48 Correct 1253 ms 21672 KB Output is correct
49 Correct 1240 ms 21692 KB Output is correct
50 Correct 1212 ms 21584 KB Output is correct
51 Correct 1238 ms 21604 KB Output is correct
52 Correct 1263 ms 21728 KB Output is correct
53 Correct 1237 ms 21584 KB Output is correct
54 Correct 1254 ms 21820 KB Output is correct
55 Correct 1226 ms 21668 KB Output is correct
56 Correct 1278 ms 21704 KB Output is correct
57 Correct 1184 ms 21800 KB Output is correct
58 Correct 1207 ms 21908 KB Output is correct
59 Correct 200 ms 9836 KB Output is correct
60 Correct 1180 ms 21728 KB Output is correct
61 Correct 1284 ms 22008 KB Output is correct
62 Correct 172 ms 13180 KB Output is correct
63 Correct 202 ms 10348 KB Output is correct
64 Correct 149 ms 12256 KB Output is correct
65 Correct 159 ms 12988 KB Output is correct
66 Correct 266 ms 10428 KB Output is correct
67 Correct 184 ms 9832 KB Output is correct
68 Correct 159 ms 12260 KB Output is correct
69 Correct 239 ms 9964 KB Output is correct
70 Correct 145 ms 12244 KB Output is correct
71 Correct 192 ms 9832 KB Output is correct
72 Correct 950 ms 24480 KB Output is correct
73 Correct 1448 ms 31416 KB Output is correct
74 Correct 1485 ms 31336 KB Output is correct
75 Correct 1491 ms 31368 KB Output is correct
76 Correct 1517 ms 31236 KB Output is correct
77 Correct 1514 ms 31356 KB Output is correct
78 Correct 1451 ms 32792 KB Output is correct
79 Correct 1506 ms 32636 KB Output is correct
80 Correct 1540 ms 32480 KB Output is correct
81 Correct 1483 ms 32848 KB Output is correct
82 Correct 1509 ms 32840 KB Output is correct
83 Correct 1544 ms 32480 KB Output is correct
84 Correct 1588 ms 33068 KB Output is correct
85 Correct 1560 ms 33060 KB Output is correct
86 Correct 1551 ms 33060 KB Output is correct
87 Correct 1502 ms 33008 KB Output is correct
88 Correct 1508 ms 33108 KB Output is correct
89 Correct 435 ms 24192 KB Output is correct
90 Correct 1551 ms 32968 KB Output is correct
91 Correct 1605 ms 32096 KB Output is correct
92 Correct 249 ms 23004 KB Output is correct
93 Correct 442 ms 22716 KB Output is correct
94 Correct 281 ms 22416 KB Output is correct
95 Correct 260 ms 22664 KB Output is correct
96 Correct 423 ms 20848 KB Output is correct
97 Correct 413 ms 23028 KB Output is correct
98 Correct 275 ms 22884 KB Output is correct
99 Correct 492 ms 22956 KB Output is correct
100 Correct 254 ms 22996 KB Output is correct