oj.uz

Submission #605093

# Submission time Handle Problem Language Result Execution time Memory
605093 2022-07-25T12:56:48 Z DanShaders Highway Tolls (IOI18_highway) C++17
90 / 100
 313 ms 10760 KB 
//Egrader.cpp
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 9e4 + 10, M = 1.3e5 + 10, INF = 0x3f3f3f3f;

struct Edge {
	int v, i;
};

vector<Edge> g[N];
int dist[N];
int order[N], by_order[N];

void find_pair(int n, vector<int> us, vector<int> vs, int a, int b) {
	int m = sz(us);
	for (int i = 0; i < m; ++i) {
		g[us[i]].push_back({vs[i], i});
		g[vs[i]].push_back({us[i], i});
	}
	int l = 1, r = n;
	ll baseline = ask(vector(m, 0));
	while (r - l > 1) {
		int mid = (l + r) / 2;
		vector w(m, 0);
		for (int i = 0; i < m; ++i) {
			if (max(us[i], vs[i]) >= mid) {
				w[i] = 1;
			}
		}
		if (baseline == ask(w)) {
			r = mid;
		} else {
			l = mid;
		}
	}

	int bound = r;

	queue<int> bfs;
	bfs.push(l);
	int cnt = 0;
	fill(all(dist), +INF);
	dist[l] = 0;
	while (sz(bfs)) {
		int u = bfs.front();
		// cout << u << endl;
		bfs.pop();
		by_order[cnt] = u;
		order[u] = cnt++;
		for (auto [v, _] : g[u]) {
			if (v < bound && dist[v] > dist[u] + 1) {
				dist[v] = dist[u] + 1;
				bfs.push(v);
			}
		}
	}

	l = 1, r = cnt;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		vector w(m, 0);
		for (int i = 0; i < m; ++i) {
			if (max(us[i], vs[i]) >= bound || max(order[us[i]], order[vs[i]]) >= mid) {
				w[i] = 1;
			}
		}
		if (baseline == ask(w)) {
			r = mid;
		} else {
			l = mid;
		}
	}

	int root = by_order[l];

	// cout << l << " " << r << endl;
	// cout << by_order[0] << " " << by_order[1] << " " << by_order[2] << endl;

	{
		bfs.push(root);
		cnt = 0;
		fill(all(dist), +INF);
		dist[root] = 0;
		while (sz(bfs)) {
			int u = bfs.front();
			bfs.pop();
			by_order[cnt] = u;
			order[u] = cnt++;
			for (auto [v, _] : g[u]) {
				if (dist[v] > dist[u] + 1) {
					dist[v] = dist[u] + 1;
					bfs.push(v);
				}
			}
		}

		l = 0, r = cnt;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			vector w(m, 0);
			for (int i = 0; i < m; ++i) {
				if (max(order[us[i]], order[vs[i]]) >= mid) {
					w[i] = 1;
				}
			}
			if (baseline == ask(w)) {
				r = mid;
			} else {
				l = mid;
			}
		}
		answer(by_order[l], root);
	}	
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2732 KB Output is correct
2 Correct 12 ms 3456 KB Output is correct
3 Correct 144 ms 8648 KB Output is correct
4 Correct 139 ms 8660 KB Output is correct
5 Correct 145 ms 8740 KB Output is correct
6 Correct 178 ms 8672 KB Output is correct
7 Correct 195 ms 8648 KB Output is correct
8 Correct 179 ms 8676 KB Output is correct
9 Correct 162 ms 8644 KB Output is correct
10 Correct 141 ms 8648 KB Output is correct
11 Correct 177 ms 8056 KB Output is correct
12 Correct 155 ms 8124 KB Output is correct
13 Correct 133 ms 8148 KB Output is correct
14 Correct 130 ms 8064 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3272 KB Output is correct
2 Correct 23 ms 4092 KB Output is correct
3 Correct 30 ms 4632 KB Output is correct
4 Correct 126 ms 8044 KB Output is correct
5 Correct 92 ms 8044 KB Output is correct
6 Correct 86 ms 8036 KB Output is correct
7 Correct 83 ms 8056 KB Output is correct
8 Correct 122 ms 8044 KB Output is correct
9 Correct 126 ms 8044 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2768 KB Output is correct
2 Correct 14 ms 3436 KB Output is correct
3 Correct 115 ms 7360 KB Output is correct
4 Correct 183 ms 8712 KB Output is correct
5 Correct 200 ms 8648 KB Output is correct
6 Correct 159 ms 8640 KB Output is correct
7 Correct 133 ms 8652 KB Output is correct
8 Correct 211 ms 8628 KB Output is correct
9 Correct 153 ms 8692 KB Output is correct
10 Correct 166 ms 8648 KB Output is correct
11 Correct 175 ms 8072 KB Output is correct
12 Correct 159 ms 8072 KB Output is correct
13 Correct 183 ms 8152 KB Output is correct
14 Correct 168 ms 8052 KB Output is correct
15 Correct 161 ms 8652 KB Output is correct
16 Correct 150 ms 8660 KB Output is correct
17 Correct 155 ms 8124 KB Output is correct
18 Correct 156 ms 8052 KB Output is correct
19 Correct 166 ms 8664 KB Output is correct
20 Correct 136 ms 8068 KB Output is correct
21 Correct 130 ms 9140 KB Output is correct
22 Correct 107 ms 9136 KB Output is correct
23 Correct 130 ms 8944 KB Output is correct
24 Correct 143 ms 8968 KB Output is correct
25 Correct 179 ms 8384 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3400 KB Output is correct
2 Correct 18 ms 3520 KB Output is correct
3 Correct 154 ms 9020 KB Output is correct
4 Correct 204 ms 9532 KB Output is correct
5 Correct 313 ms 10512 KB Output is correct
6 Correct 277 ms 10436 KB Output is correct
7 Correct 238 ms 10540 KB Output is correct
8 Correct 202 ms 10504 KB Output is correct
9 Correct 169 ms 8556 KB Output is correct
10 Correct 174 ms 9032 KB Output is correct
11 Correct 195 ms 9316 KB Output is correct
12 Correct 174 ms 10176 KB Output is correct
13 Correct 252 ms 10264 KB Output is correct
14 Correct 224 ms 10528 KB Output is correct
15 Correct 243 ms 10444 KB Output is correct
16 Correct 234 ms 9496 KB Output is correct
17 Correct 137 ms 9180 KB Output is correct
18 Correct 144 ms 9372 KB Output is correct
19 Correct 162 ms 9336 KB Output is correct
20 Correct 183 ms 9380 KB Output is correct
21 Correct 197 ms 10428 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3496 KB Output is correct
2 Correct 19 ms 3528 KB Output is correct
3 Correct 192 ms 9228 KB Output is correct
4 Partially correct 183 ms 9232 KB Output is partially correct
5 Correct 245 ms 9484 KB Output is correct
6 Correct 217 ms 10432 KB Output is correct
7 Correct 156 ms 9044 KB Output is correct
8 Partially correct 155 ms 9328 KB Output is partially correct
9 Partially correct 192 ms 9480 KB Output is partially correct
10 Partially correct 236 ms 10448 KB Output is partially correct
11 Correct 221 ms 10536 KB Output is correct
12 Partially correct 215 ms 10480 KB Output is partially correct
13 Correct 179 ms 9240 KB Output is correct
14 Correct 213 ms 9076 KB Output is correct
15 Correct 187 ms 9312 KB Output is correct
16 Correct 159 ms 9028 KB Output is correct
17 Correct 194 ms 9236 KB Output is correct
18 Correct 164 ms 9092 KB Output is correct
19 Correct 255 ms 10088 KB Output is correct
20 Correct 242 ms 10296 KB Output is correct
21 Correct 230 ms 10760 KB Output is correct
22 Correct 192 ms 10496 KB Output is correct
23 Correct 261 ms 10420 KB Output is correct
24 Partially correct 187 ms 10480 KB Output is partially correct
25 Partially correct 265 ms 10560 KB Output is partially correct
26 Correct 255 ms 10460 KB Output is correct
27 Correct 168 ms 9328 KB Output is correct
28 Partially correct 123 ms 9224 KB Output is partially correct
29 Correct 137 ms 9572 KB Output is correct
30 Partially correct 130 ms 9312 KB Output is partially correct
31 Correct 194 ms 9264 KB Output is correct
32 Correct 162 ms 9200 KB Output is correct
33 Partially correct 151 ms 9436 KB Output is partially correct
34 Correct 131 ms 9412 KB Output is correct
35 Partially correct 126 ms 9272 KB Output is partially correct
36 Correct 123 ms 9176 KB Output is correct
37 Correct 167 ms 9420 KB Output is correct
38 Correct 141 ms 9516 KB Output is correct
39 Correct 204 ms 10436 KB Output is correct
40 Correct 198 ms 10428 KB Output is correct
41 Correct 187 ms 10536 KB Output is correct
42 Correct 197 ms 10456 KB Output is correct