oj.uz

Submission #799415

# Submission time Handle Problem Language Result Execution time Memory
799415 2023-07-31T13:58:28 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
90 / 100
 234 ms 41980 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;
#define all(x)		(x).begin(), (x).end()

const int MAXN = 1e6 + 10;

bool bad[MAXN];
int askcnt = 0;
int from[MAXN], to[MAXN], n, m, par[MAXN], mn;
vector<int> adj[MAXN], dfs_order, fuck;

inline int f(int ind, int v) {
	return from[ind] ^ to[ind] ^ v;
}

void dfs(int v, int p) {
	dfs_order.push_back(v);
	for (int ind : adj[v]) {
		int u = f(ind, v);
		if (u == p) continue;
		if (bad[u]) continue;

		par[u] = ind;
		dfs(u, v);
	}
}


inline vector<int> seg(int l, int r) {
	vector<int> ans;
	for (int i = l; i <= r; i++)
		ans.push_back(par[dfs_order[i]]);

	return ans;
}

inline int get(vector<int> vec) {
	askcnt++;
	assert(askcnt <= 90);
	vector<int> W(m);
	for (int i = 0; i < m; i++) W[i] = 1;
	for (int e : fuck)
		W[e] = 0;

	for (int e : vec)
		W[e] = 1;

	return ask(W);
}

inline int getp(vector<int> vec) {
	askcnt++;
	assert(askcnt <= 90);
	vector<int> W(m);
	for (int i = 0; i < m; i++) 
		W[i] = 1;
	for (int e : vec)
		W[e] = 0;

	return ask(W);
}

inline int get(int l, int r) {
	return get(seg(l, r));
}

inline int getp(int l, int r) {
	return getp(seg(l, r));
}

inline int find(int root) {
	par[root] = -1;
	dfs_order.clear();

	dfs(root, root);

	int l = 1, r = int(dfs_order.size()) - 1;

	while (l < r) {
		int mid = (l + r) >> 1;	
		if (getp(1, mid) == mn) r = mid;
		else l = mid + 1;
	}

	return dfs_order[l];

}

int dist[MAXN];

const double Z = 0.45;

int fucking_root;

inline vector<int> random_spt() {
	vector<int> ans;
	queue<int> q;

	int l = 0, r = n - 1;
	while (l < r) {
		int len = r - l;
		int mid = l + Z * len;
		mid = max(mid, l);
		mid = min(mid, r - 1);

		vector<int> W(m);
	
		for (int i = 0; i < m; i++)
			if (from[i] <= mid || to[i] <= mid)
				W[i] = 1;

		if (ask(W) == mn) {
			for (int i = l; i <= mid; i++) bad[i] = true;
			l = mid + 1;
		} else r = mid;
	}

	int v = l;
	fucking_root = v;

	memset(dist, 63, sizeof dist);
	q.push(v);
	dist[v] = 0;

	while (!q.empty()) {
		int v = q.front();
		q.pop();

		if (v < fucking_root) continue;

		for (int ind : adj[v]) {
			int u = f(ind, v);
			if (u < fucking_root) continue;
			if (dist[u] > dist[v] + 1) {
				dist[u] = dist[v] + 1;
				q.push(u);
				ans.push_back(ind);
			}
		}
	}

	return ans;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	m = U.size();
	n = N;

	for (int i = 0; i < m; i++) {
		from[i] = U[i];
		to[i] = V[i];

		adj[from[i]].push_back(i);
		adj[to[i]].push_back(i);
	}

	for (int i = 0; i < m; i++)
		fuck.push_back(i);

	mn = get({});
	vector<int> tmp = random_spt();

	fuck = tmp;
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int ind : tmp) {
		adj[from[ind]].push_back(ind);
		adj[to[ind]].push_back(ind);
	}


	int v = find(fucking_root);
	int u = find(v);
	
	cerr << u << sep << v << endl;

	answer(u, v);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27728 KB Output is correct
2 Correct 15 ms 27728 KB Output is correct
3 Correct 14 ms 27648 KB Output is correct
4 Correct 14 ms 27720 KB Output is correct
5 Correct 15 ms 27744 KB Output is correct
6 Correct 15 ms 27676 KB Output is correct
7 Correct 15 ms 27744 KB Output is correct
8 Correct 15 ms 27744 KB Output is correct
9 Correct 19 ms 27728 KB Output is correct
10 Correct 14 ms 27672 KB Output is correct
11 Correct 14 ms 27676 KB Output is correct
12 Correct 19 ms 27688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27768 KB Output is correct
2 Correct 26 ms 28584 KB Output is correct
3 Correct 135 ms 35072 KB Output is correct
4 Correct 150 ms 34964 KB Output is correct
5 Correct 126 ms 34976 KB Output is correct
6 Correct 137 ms 35080 KB Output is correct
7 Correct 136 ms 35076 KB Output is correct
8 Correct 132 ms 35060 KB Output is correct
9 Correct 132 ms 35088 KB Output is correct
10 Correct 117 ms 35076 KB Output is correct
11 Correct 119 ms 36620 KB Output is correct
12 Correct 135 ms 37600 KB Output is correct
13 Correct 144 ms 36760 KB Output is correct
14 Correct 135 ms 36788 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29136 KB Output is correct
2 Correct 29 ms 30568 KB Output is correct
3 Correct 49 ms 30048 KB Output is correct
4 Correct 91 ms 38672 KB Output is correct
5 Correct 108 ms 38756 KB Output is correct
6 Correct 82 ms 40392 KB Output is correct
7 Correct 83 ms 33944 KB Output is correct
8 Correct 108 ms 39620 KB Output is correct
9 Correct 102 ms 41980 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27740 KB Output is correct
2 Correct 25 ms 28576 KB Output is correct
3 Correct 109 ms 33324 KB Output is correct
4 Correct 121 ms 34220 KB Output is correct
5 Correct 120 ms 34704 KB Output is correct
6 Correct 132 ms 33804 KB Output is correct
7 Correct 92 ms 34516 KB Output is correct
8 Correct 122 ms 34352 KB Output is correct
9 Correct 138 ms 35068 KB Output is correct
10 Correct 131 ms 34976 KB Output is correct
11 Correct 141 ms 36124 KB Output is correct
12 Correct 134 ms 37500 KB Output is correct
13 Correct 136 ms 36876 KB Output is correct
14 Correct 138 ms 37396 KB Output is correct
15 Correct 105 ms 34968 KB Output is correct
16 Correct 148 ms 34216 KB Output is correct
17 Correct 150 ms 35916 KB Output is correct
18 Correct 110 ms 35260 KB Output is correct
19 Correct 89 ms 33656 KB Output is correct
20 Correct 132 ms 34124 KB Output is correct
21 Correct 108 ms 35036 KB Output is correct
22 Correct 130 ms 34556 KB Output is correct
23 Correct 96 ms 35416 KB Output is correct
24 Correct 103 ms 36084 KB Output is correct
25 Correct 164 ms 41248 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28596 KB Output is correct
2 Correct 28 ms 28616 KB Output is correct
3 Correct 156 ms 35372 KB Output is correct
4 Correct 136 ms 35616 KB Output is correct
5 Correct 234 ms 36744 KB Output is correct
6 Correct 172 ms 36320 KB Output is correct
7 Correct 171 ms 36720 KB Output is correct
8 Correct 164 ms 36768 KB Output is correct
9 Correct 144 ms 33680 KB Output is correct
10 Correct 156 ms 34100 KB Output is correct
11 Correct 155 ms 33884 KB Output is correct
12 Correct 185 ms 35968 KB Output is correct
13 Correct 193 ms 36200 KB Output is correct
14 Correct 178 ms 36264 KB Output is correct
15 Correct 175 ms 36272 KB Output is correct
16 Correct 150 ms 35364 KB Output is correct
17 Correct 123 ms 35296 KB Output is correct
18 Correct 153 ms 35372 KB Output is correct
19 Correct 108 ms 35392 KB Output is correct
20 Correct 110 ms 35036 KB Output is correct
21 Correct 179 ms 36872 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28612 KB Output is correct
2 Correct 29 ms 28644 KB Output is correct
3 Correct 148 ms 35280 KB Output is correct
4 Partially correct 179 ms 35480 KB Output is partially correct
5 Correct 157 ms 35552 KB Output is correct
6 Partially correct 175 ms 36812 KB Output is partially correct
7 Correct 158 ms 35324 KB Output is correct
8 Partially correct 143 ms 35636 KB Output is partially correct
9 Correct 162 ms 35724 KB Output is correct
10 Correct 224 ms 36860 KB Output is correct
11 Correct 219 ms 36700 KB Output is correct
12 Correct 183 ms 36776 KB Output is correct
13 Correct 136 ms 34020 KB Output is correct
14 Correct 150 ms 34324 KB Output is correct
15 Correct 127 ms 34188 KB Output is correct
16 Correct 157 ms 34320 KB Output is correct
17 Correct 152 ms 33868 KB Output is correct
18 Correct 154 ms 34440 KB Output is correct
19 Correct 144 ms 35960 KB Output is correct
20 Correct 152 ms 36304 KB Output is correct
21 Correct 212 ms 36536 KB Output is correct
22 Partially correct 208 ms 36280 KB Output is partially correct
23 Correct 203 ms 36688 KB Output is correct
24 Correct 195 ms 36252 KB Output is correct
25 Correct 172 ms 35880 KB Output is correct
26 Correct 174 ms 36392 KB Output is correct
27 Correct 145 ms 35272 KB Output is correct
28 Correct 103 ms 35216 KB Output is correct
29 Correct 124 ms 35308 KB Output is correct
30 Correct 129 ms 35452 KB Output is correct
31 Correct 124 ms 35332 KB Output is correct
32 Correct 135 ms 35096 KB Output is correct
33 Correct 148 ms 35432 KB Output is correct
34 Correct 104 ms 35356 KB Output is correct
35 Correct 127 ms 35436 KB Output is correct
36 Correct 156 ms 35184 KB Output is correct
37 Correct 113 ms 35048 KB Output is correct
38 Correct 120 ms 35932 KB Output is correct
39 Partially correct 157 ms 37236 KB Output is partially correct
40 Correct 178 ms 37436 KB Output is correct
41 Correct 175 ms 36668 KB Output is correct
42 Correct 137 ms 36688 KB Output is correct