oj.uz

Submission #289387

# Submission time Handle Problem Language Result Execution time Memory
289387 2020-09-02T15:48:48 Z dolphingarlic Highway Tolls (IOI18_highway) C++14
100 / 100
 302 ms 10972 KB 
#include "highway.h"

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> graph[90000], ord[2];
bool visited[90000];
int ans[2];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M = int(U.size());
	for (int i = 0; i < M; i++) {
		graph[U[i]].push_back({V[i], i});
		graph[V[i]].push_back({U[i], i});
	}

	vector<int> W(M, 0);
	long long path_len = ask(W) / A;

	int l = 0, r = M - 1;
	while (l != r) {
		int mid = (l + r) / 2;
		fill(W.begin(), W.end(), 0);
		for (int i = 0; i <= mid; i++) W[i] = 1;
		long long res = ask(W);
		if (res == path_len * A) l = mid + 1;
		else r = mid;
	}
	int m_edge = l, uu = U[l], vv = V[l];

	visited[uu] = visited[vv] = true;
	queue<pair<int, int>> q;
	q.push({uu, 0}); q.push({vv, 1});
	ord[0].push_back({uu, -1}); ord[1].push_back({vv, -1});
	while (q.size()) {
		int curr, sub;
		tie(curr, sub) = q.front();
		q.pop();
		for (pair<int, int> i : graph[curr]) {
			if (!visited[i.first] && i.second > m_edge) {
				visited[i.first] = true;
				ord[sub].push_back(i);
				q.push({i.first, sub});
			}
		}
	}

	for (int s = 0; s < 2; s++) {
		l = 0, r = ord[s].size() - 1;
		while (l != r) {
			int mid = (l + r) / 2;
			fill(W.begin(), W.end(), 1);
			W[m_edge] = 0;
			for (pair<int, int> i : ord[1 - s]) if (i.second != -1) W[i.second] = 0;
			for (int i = 1; i <= mid; i++) W[ord[s][i].second] = 0;
			long long dist = ask(W);
			if (dist == path_len * A) r = mid;
			else l = mid + 1;
		}
		ans[s] = ord[s][l].first;
	}

	answer(ans[0], ans[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2432 KB Output is correct
2 Correct 2 ms 2432 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 2 ms 2432 KB Output is correct
5 Correct 2 ms 2432 KB Output is correct
6 Correct 3 ms 2432 KB Output is correct
7 Correct 2 ms 2432 KB Output is correct
8 Correct 2 ms 2432 KB Output is correct
9 Correct 2 ms 2432 KB Output is correct
10 Correct 2 ms 2432 KB Output is correct
11 Correct 2 ms 2432 KB Output is correct
12 Correct 3 ms 2432 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2560 KB Output is correct
2 Correct 14 ms 3200 KB Output is correct
3 Correct 182 ms 8852 KB Output is correct
4 Correct 204 ms 8828 KB Output is correct
5 Correct 155 ms 8832 KB Output is correct
6 Correct 136 ms 8336 KB Output is correct
7 Correct 151 ms 8312 KB Output is correct
8 Correct 157 ms 8852 KB Output is correct
9 Correct 137 ms 8336 KB Output is correct
10 Correct 164 ms 8400 KB Output is correct
11 Correct 179 ms 7384 KB Output is correct
12 Correct 200 ms 7956 KB Output is correct
13 Correct 194 ms 8436 KB Output is correct
14 Correct 195 ms 8552 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3200 KB Output is correct
2 Correct 35 ms 3832 KB Output is correct
3 Correct 35 ms 4032 KB Output is correct
4 Correct 156 ms 7708 KB Output is correct
5 Correct 115 ms 7704 KB Output is correct
6 Correct 108 ms 8244 KB Output is correct
7 Correct 110 ms 7204 KB Output is correct
8 Correct 157 ms 7764 KB Output is correct
9 Correct 107 ms 7688 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2560 KB Output is correct
2 Correct 16 ms 3072 KB Output is correct
3 Correct 107 ms 7708 KB Output is correct
4 Correct 137 ms 8844 KB Output is correct
5 Correct 125 ms 7760 KB Output is correct
6 Correct 122 ms 7768 KB Output is correct
7 Correct 174 ms 8340 KB Output is correct
8 Correct 131 ms 7964 KB Output is correct
9 Correct 158 ms 8932 KB Output is correct
10 Correct 198 ms 8408 KB Output is correct
11 Correct 160 ms 8328 KB Output is correct
12 Correct 158 ms 7904 KB Output is correct
13 Correct 165 ms 7816 KB Output is correct
14 Correct 138 ms 7524 KB Output is correct
15 Correct 161 ms 7772 KB Output is correct
16 Correct 125 ms 7676 KB Output is correct
17 Correct 199 ms 8352 KB Output is correct
18 Correct 156 ms 8324 KB Output is correct
19 Correct 96 ms 7720 KB Output is correct
20 Correct 165 ms 7224 KB Output is correct
21 Correct 166 ms 8944 KB Output is correct
22 Correct 161 ms 8328 KB Output is correct
23 Correct 175 ms 9192 KB Output is correct
24 Correct 138 ms 9280 KB Output is correct
25 Correct 167 ms 8440 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3192 KB Output is correct
2 Correct 24 ms 3320 KB Output is correct
3 Correct 173 ms 9320 KB Output is correct
4 Correct 234 ms 9348 KB Output is correct
5 Correct 283 ms 10300 KB Output is correct
6 Correct 302 ms 10384 KB Output is correct
7 Correct 295 ms 10408 KB Output is correct
8 Correct 199 ms 10556 KB Output is correct
9 Correct 159 ms 7944 KB Output is correct
10 Correct 226 ms 8904 KB Output is correct
11 Correct 186 ms 9168 KB Output is correct
12 Correct 265 ms 10176 KB Output is correct
13 Correct 225 ms 10500 KB Output is correct
14 Correct 255 ms 10332 KB Output is correct
15 Correct 248 ms 10764 KB Output is correct
16 Correct 229 ms 9424 KB Output is correct
17 Correct 140 ms 8860 KB Output is correct
18 Correct 124 ms 8400 KB Output is correct
19 Correct 140 ms 9576 KB Output is correct
20 Correct 179 ms 8656 KB Output is correct
21 Correct 286 ms 10752 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3200 KB Output is correct
2 Correct 18 ms 3416 KB Output is correct
3 Correct 174 ms 9164 KB Output is correct
4 Correct 237 ms 9244 KB Output is correct
5 Correct 184 ms 9508 KB Output is correct
6 Correct 277 ms 10624 KB Output is correct
7 Correct 162 ms 9260 KB Output is correct
8 Correct 178 ms 9568 KB Output is correct
9 Correct 192 ms 9420 KB Output is correct
10 Correct 226 ms 10448 KB Output is correct
11 Correct 245 ms 10400 KB Output is correct
12 Correct 210 ms 10520 KB Output is correct
13 Correct 161 ms 8472 KB Output is correct
14 Correct 154 ms 8452 KB Output is correct
15 Correct 184 ms 9316 KB Output is correct
16 Correct 232 ms 8912 KB Output is correct
17 Correct 246 ms 9108 KB Output is correct
18 Correct 183 ms 9088 KB Output is correct
19 Correct 286 ms 10188 KB Output is correct
20 Correct 226 ms 10648 KB Output is correct
21 Correct 232 ms 10444 KB Output is correct
22 Correct 293 ms 10416 KB Output is correct
23 Correct 296 ms 10616 KB Output is correct
24 Correct 245 ms 10496 KB Output is correct
25 Correct 280 ms 10732 KB Output is correct
26 Correct 288 ms 10824 KB Output is correct
27 Correct 138 ms 8768 KB Output is correct
28 Correct 139 ms 9596 KB Output is correct
29 Correct 129 ms 9720 KB Output is correct
30 Correct 130 ms 9612 KB Output is correct
31 Correct 137 ms 9568 KB Output is correct
32 Correct 142 ms 9540 KB Output is correct
33 Correct 170 ms 9808 KB Output is correct
34 Correct 137 ms 8900 KB Output is correct
35 Correct 144 ms 9060 KB Output is correct
36 Correct 138 ms 9608 KB Output is correct
37 Correct 146 ms 9292 KB Output is correct
38 Correct 141 ms 9596 KB Output is correct
39 Correct 240 ms 10972 KB Output is correct
40 Correct 222 ms 10740 KB Output is correct
41 Correct 233 ms 10640 KB Output is correct
42 Correct 227 ms 10380 KB Output is correct