oj.uz

Submission #799429

# Submission time Handle Problem Language Result Execution time Memory
799429 2023-07-31T14:13:21 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
90 / 100
 241 ms 43408 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, jahel;
int fucking_root, A, B;

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

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

		if (d == mn / A)
			jahel.push_back(v);

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


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, int tof = 0) {
	par[root] = -1;
	dfs_order.clear();
	jahel.clear();

	dfs(root, root);

	if (tof) dfs_order = jahel;

	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.5;

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;
	A = A_;
	B = B_;

	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 15 ms 27728 KB Output is correct
2 Correct 14 ms 27728 KB Output is correct
3 Correct 16 ms 27728 KB Output is correct
4 Correct 15 ms 27644 KB Output is correct
5 Correct 14 ms 27728 KB Output is correct
6 Correct 15 ms 27728 KB Output is correct
7 Correct 15 ms 27660 KB Output is correct
8 Correct 15 ms 27680 KB Output is correct
9 Correct 15 ms 27648 KB Output is correct
10 Correct 15 ms 27728 KB Output is correct
11 Correct 14 ms 27680 KB Output is correct
12 Correct 15 ms 27652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27728 KB Output is correct
2 Correct 25 ms 28572 KB Output is correct
3 Correct 136 ms 35188 KB Output is correct
4 Correct 131 ms 35064 KB Output is correct
5 Correct 121 ms 34992 KB Output is correct
6 Correct 112 ms 35124 KB Output is correct
7 Correct 127 ms 35156 KB Output is correct
8 Correct 122 ms 35064 KB Output is correct
9 Correct 134 ms 35100 KB Output is correct
10 Correct 142 ms 35140 KB Output is correct
11 Correct 131 ms 36976 KB Output is correct
12 Correct 140 ms 38136 KB Output is correct
13 Correct 159 ms 37292 KB Output is correct
14 Correct 133 ms 37164 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29264 KB Output is correct
2 Correct 39 ms 30824 KB Output is correct
3 Correct 41 ms 30104 KB Output is correct
4 Correct 98 ms 39664 KB Output is correct
5 Correct 87 ms 39776 KB Output is correct
6 Correct 111 ms 41640 KB Output is correct
7 Correct 90 ms 34036 KB Output is correct
8 Correct 138 ms 40720 KB Output is correct
9 Correct 87 ms 43408 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27820 KB Output is correct
2 Correct 27 ms 28576 KB Output is correct
3 Correct 109 ms 33332 KB Output is correct
4 Correct 143 ms 34220 KB Output is correct
5 Correct 99 ms 34704 KB Output is correct
6 Correct 110 ms 33812 KB Output is correct
7 Correct 115 ms 34512 KB Output is correct
8 Correct 100 ms 34356 KB Output is correct
9 Correct 116 ms 35076 KB Output is correct
10 Correct 131 ms 35104 KB Output is correct
11 Correct 138 ms 36420 KB Output is correct
12 Correct 133 ms 38004 KB Output is correct
13 Correct 149 ms 37252 KB Output is correct
14 Correct 123 ms 37892 KB Output is correct
15 Correct 122 ms 34968 KB Output is correct
16 Correct 110 ms 34204 KB Output is correct
17 Correct 149 ms 36344 KB Output is correct
18 Correct 110 ms 35528 KB Output is correct
19 Correct 114 ms 33660 KB Output is correct
20 Correct 106 ms 34204 KB Output is correct
21 Correct 111 ms 34960 KB Output is correct
22 Correct 125 ms 34552 KB Output is correct
23 Correct 149 ms 35480 KB Output is correct
24 Correct 138 ms 36236 KB Output is correct
25 Correct 149 ms 42564 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28600 KB Output is correct
2 Correct 32 ms 28648 KB Output is correct
3 Correct 175 ms 35468 KB Output is correct
4 Correct 140 ms 35644 KB Output is correct
5 Correct 207 ms 36804 KB Output is correct
6 Correct 207 ms 36368 KB Output is correct
7 Correct 168 ms 36744 KB Output is correct
8 Correct 170 ms 36804 KB Output is correct
9 Correct 116 ms 33764 KB Output is correct
10 Correct 121 ms 34148 KB Output is correct
11 Correct 185 ms 33892 KB Output is correct
12 Correct 166 ms 36056 KB Output is correct
13 Correct 221 ms 36372 KB Output is correct
14 Correct 203 ms 36284 KB Output is correct
15 Correct 217 ms 36376 KB Output is correct
16 Correct 212 ms 35396 KB Output is correct
17 Correct 109 ms 35300 KB Output is correct
18 Correct 150 ms 35388 KB Output is correct
19 Correct 134 ms 35396 KB Output is correct
20 Correct 93 ms 35028 KB Output is correct
21 Correct 191 ms 36856 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28620 KB Output is correct
2 Correct 29 ms 28628 KB Output is correct
3 Correct 138 ms 35284 KB Output is correct
4 Partially correct 163 ms 35528 KB Output is partially correct
5 Correct 164 ms 35608 KB Output is correct
6 Partially correct 183 ms 36824 KB Output is partially correct
7 Correct 136 ms 35376 KB Output is correct
8 Partially correct 157 ms 35676 KB Output is partially correct
9 Partially correct 171 ms 35788 KB Output is partially correct
10 Correct 217 ms 36968 KB Output is correct
11 Correct 194 ms 37056 KB Output is correct
12 Correct 205 ms 36888 KB Output is correct
13 Correct 173 ms 34056 KB Output is correct
14 Correct 134 ms 34416 KB Output is correct
15 Correct 158 ms 34376 KB Output is correct
16 Correct 153 ms 34468 KB Output is correct
17 Correct 146 ms 33880 KB Output is correct
18 Correct 184 ms 34436 KB Output is correct
19 Correct 151 ms 35952 KB Output is correct
20 Correct 208 ms 36324 KB Output is correct
21 Correct 224 ms 36584 KB Output is correct
22 Correct 203 ms 36236 KB Output is correct
23 Partially correct 241 ms 36684 KB Output is partially correct
24 Partially correct 212 ms 36436 KB Output is partially correct
25 Correct 150 ms 35944 KB Output is correct
26 Correct 149 ms 36468 KB Output is correct
27 Correct 129 ms 35232 KB Output is correct
28 Correct 138 ms 35204 KB Output is correct
29 Correct 110 ms 35272 KB Output is correct
30 Partially correct 122 ms 35448 KB Output is partially correct
31 Correct 123 ms 35300 KB Output is correct
32 Correct 128 ms 35040 KB Output is correct
33 Correct 107 ms 35436 KB Output is correct
34 Correct 151 ms 35436 KB Output is correct
35 Correct 134 ms 35488 KB Output is correct
36 Correct 105 ms 35148 KB Output is correct
37 Correct 116 ms 35152 KB Output is correct
38 Partially correct 133 ms 35940 KB Output is partially correct
39 Partially correct 170 ms 37392 KB Output is partially correct
40 Correct 208 ms 37592 KB Output is correct
41 Partially correct 196 ms 36888 KB Output is partially correct
42 Correct 146 ms 36816 KB Output is correct