oj.uz

Submission #799454

# Submission time Handle Problem Language Result Execution time Memory
799454 2023-07-31T14:45:53 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
90 / 100
 617 ms 44120 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#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;
ll from[MAXN], to[MAXN], n, m, par[MAXN], mn;
vector<int> adj[MAXN], dfs_order, fuck, jahel;
ll 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);

	if (d == mn / A)
		jahel.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, 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);

	debug(root)
	jahel.insert(jahel.begin(), 0);

	int l = 1, r = int(dfs_order.size()) - 1;
	tof = 0;
	if (tof) r = int(jahel.size()) - 1;

	for (int e : dfs_order) cerr << e << sep;
	cerr << endl;

	while (l < r) {
		int mid = (l + r) >> 1;
		int tmid = mid;
		if (tof) {
			tmid = 1;
			while (dfs_order[tmid] != jahel[mid]) tmid++;
		}

		if (getp(1, tmid) == mn) r = mid;
		else l = mid + 1;
	}

	return (tof ? jahel[l] : dfs_order[l]);

}

int dist[MAXN];

const double Z = 0.45;

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, 1);

	cerr << u << sep << v << endl;

	answer(u, v);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27728 KB Output is correct
2 Correct 15 ms 27672 KB Output is correct
3 Correct 14 ms 27692 KB Output is correct
4 Correct 14 ms 27680 KB Output is correct
5 Correct 14 ms 27672 KB Output is correct
6 Correct 14 ms 27728 KB Output is correct
7 Correct 14 ms 27728 KB Output is correct
8 Correct 15 ms 27632 KB Output is correct
9 Correct 14 ms 27728 KB Output is correct
10 Correct 14 ms 27728 KB Output is correct
11 Correct 14 ms 27660 KB Output is correct
12 Correct 14 ms 27680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27744 KB Output is correct
2 Correct 65 ms 28680 KB Output is correct
3 Correct 515 ms 37268 KB Output is correct
4 Correct 524 ms 37112 KB Output is correct
5 Correct 491 ms 37252 KB Output is correct
6 Correct 492 ms 37392 KB Output is correct
7 Correct 480 ms 37396 KB Output is correct
8 Correct 521 ms 37140 KB Output is correct
9 Correct 492 ms 37268 KB Output is correct
10 Correct 506 ms 37256 KB Output is correct
11 Correct 540 ms 38664 KB Output is correct
12 Correct 496 ms 39684 KB Output is correct
13 Correct 528 ms 38900 KB Output is correct
14 Correct 518 ms 39032 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 29420 KB Output is correct
2 Correct 97 ms 30968 KB Output is correct
3 Correct 56 ms 30332 KB Output is correct
4 Correct 316 ms 40400 KB Output is correct
5 Correct 347 ms 40520 KB Output is correct
6 Correct 411 ms 42212 KB Output is correct
7 Correct 120 ms 34744 KB Output is correct
8 Correct 344 ms 41476 KB Output is correct
9 Correct 497 ms 44120 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27728 KB Output is correct
2 Correct 65 ms 28688 KB Output is correct
3 Correct 252 ms 34580 KB Output is correct
4 Correct 218 ms 35576 KB Output is correct
5 Correct 392 ms 36512 KB Output is correct
6 Correct 102 ms 34836 KB Output is correct
7 Correct 264 ms 36020 KB Output is correct
8 Correct 235 ms 35708 KB Output is correct
9 Correct 507 ms 37208 KB Output is correct
10 Correct 471 ms 37200 KB Output is correct
11 Correct 521 ms 38528 KB Output is correct
12 Correct 501 ms 39632 KB Output is correct
13 Correct 488 ms 39060 KB Output is correct
14 Correct 524 ms 39472 KB Output is correct
15 Correct 380 ms 36580 KB Output is correct
16 Correct 213 ms 35512 KB Output is correct
17 Correct 377 ms 37856 KB Output is correct
18 Correct 199 ms 36936 KB Output is correct
19 Correct 110 ms 34392 KB Output is correct
20 Correct 113 ms 35288 KB Output is correct
21 Correct 390 ms 36804 KB Output is correct
22 Correct 297 ms 36248 KB Output is correct
23 Correct 490 ms 37816 KB Output is correct
24 Correct 485 ms 38476 KB Output is correct
25 Correct 499 ms 43404 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 28736 KB Output is correct
2 Correct 65 ms 29000 KB Output is correct
3 Correct 507 ms 37604 KB Output is correct
4 Correct 452 ms 37708 KB Output is correct
5 Correct 528 ms 38856 KB Output is correct
6 Correct 475 ms 38544 KB Output is correct
7 Correct 560 ms 38872 KB Output is correct
8 Correct 505 ms 38736 KB Output is correct
9 Correct 237 ms 34972 KB Output is correct
10 Correct 186 ms 35312 KB Output is correct
11 Correct 194 ms 35064 KB Output is correct
12 Correct 424 ms 37784 KB Output is correct
13 Correct 492 ms 38408 KB Output is correct
14 Correct 543 ms 38712 KB Output is correct
15 Correct 580 ms 38680 KB Output is correct
16 Correct 326 ms 36980 KB Output is correct
17 Correct 428 ms 37564 KB Output is correct
18 Correct 394 ms 37172 KB Output is correct
19 Correct 498 ms 37812 KB Output is correct
20 Correct 290 ms 36884 KB Output is correct
21 Correct 528 ms 39164 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 28776 KB Output is correct
2 Correct 66 ms 29092 KB Output is correct
3 Correct 438 ms 37172 KB Output is correct
4 Partially correct 483 ms 37520 KB Output is partially correct
5 Correct 467 ms 37656 KB Output is correct
6 Partially correct 538 ms 39040 KB Output is partially correct
7 Correct 497 ms 37432 KB Output is correct
8 Partially correct 538 ms 38108 KB Output is partially correct
9 Correct 551 ms 37992 KB Output is correct
10 Correct 544 ms 39124 KB Output is correct
11 Correct 571 ms 39320 KB Output is correct
12 Correct 576 ms 39076 KB Output is correct
13 Correct 205 ms 35288 KB Output is correct
14 Correct 223 ms 35720 KB Output is correct
15 Correct 237 ms 35748 KB Output is correct
16 Correct 234 ms 35800 KB Output is correct
17 Correct 156 ms 34992 KB Output is correct
18 Correct 253 ms 36072 KB Output is correct
19 Correct 449 ms 37864 KB Output is correct
20 Correct 500 ms 38096 KB Output is correct
21 Correct 493 ms 38464 KB Output is correct
22 Partially correct 543 ms 38324 KB Output is partially correct
23 Correct 552 ms 38988 KB Output is correct
24 Correct 521 ms 38656 KB Output is correct
25 Correct 374 ms 37736 KB Output is correct
26 Correct 531 ms 38832 KB Output is correct
27 Correct 393 ms 36932 KB Output is correct
28 Correct 348 ms 36940 KB Output is correct
29 Correct 307 ms 37044 KB Output is correct
30 Correct 526 ms 37588 KB Output is correct
31 Correct 340 ms 37100 KB Output is correct
32 Correct 310 ms 36552 KB Output is correct
33 Correct 387 ms 37152 KB Output is correct
34 Correct 450 ms 37900 KB Output is correct
35 Correct 489 ms 37884 KB Output is correct
36 Correct 353 ms 36856 KB Output is correct
37 Correct 299 ms 36900 KB Output is correct
38 Correct 527 ms 38136 KB Output is correct
39 Partially correct 524 ms 39608 KB Output is partially correct
40 Correct 573 ms 39744 KB Output is correct
41 Correct 617 ms 39088 KB Output is correct
42 Correct 550 ms 39128 KB Output is correct