oj.uz

Submission #799477

# Submission time Handle Problem Language Result Execution time Memory
799477 2023-07-31T14:57:41 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
100 / 100
 572 ms 49572 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int		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<int32_t> 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<int32_t> 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 = find(all(dfs_order), jahel[mid]) - dfs_order.begin();
			assert(tmid < dfs_order.size());
		}

		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<int32_t> 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(int32_t N, std::vector<int32_t> U, std::vector<int32_t> V, int32_t A_, int32_t 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);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from highway.cpp:2:
highway.cpp: In function 'll find(ll, ll)':
highway.cpp:107:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |    assert(tmid < dfs_order.size());
      |           ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31568 KB Output is correct
2 Correct 16 ms 31640 KB Output is correct
3 Correct 16 ms 31596 KB Output is correct
4 Correct 15 ms 31632 KB Output is correct
5 Correct 15 ms 31636 KB Output is correct
6 Correct 17 ms 31568 KB Output is correct
7 Correct 15 ms 31568 KB Output is correct
8 Correct 16 ms 31660 KB Output is correct
9 Correct 15 ms 31568 KB Output is correct
10 Correct 15 ms 31568 KB Output is correct
11 Correct 15 ms 31568 KB Output is correct
12 Correct 17 ms 31568 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31696 KB Output is correct
2 Correct 63 ms 32864 KB Output is correct
3 Correct 480 ms 43692 KB Output is correct
4 Correct 506 ms 42896 KB Output is correct
5 Correct 487 ms 42864 KB Output is correct
6 Correct 462 ms 43412 KB Output is correct
7 Correct 506 ms 43604 KB Output is correct
8 Correct 505 ms 43784 KB Output is correct
9 Correct 549 ms 43340 KB Output is correct
10 Correct 500 ms 43816 KB Output is correct
11 Correct 507 ms 44124 KB Output is correct
12 Correct 493 ms 44808 KB Output is correct
13 Correct 475 ms 44020 KB Output is correct
14 Correct 495 ms 43808 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 33484 KB Output is correct
2 Correct 104 ms 35040 KB Output is correct
3 Correct 59 ms 34348 KB Output is correct
4 Correct 293 ms 45356 KB Output is correct
5 Correct 307 ms 45360 KB Output is correct
6 Correct 396 ms 47244 KB Output is correct
7 Correct 110 ms 39228 KB Output is correct
8 Correct 360 ms 46496 KB Output is correct
9 Correct 168 ms 41328 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31764 KB Output is correct
2 Correct 64 ms 32900 KB Output is correct
3 Correct 270 ms 40000 KB Output is correct
4 Correct 227 ms 41072 KB Output is correct
5 Correct 364 ms 42376 KB Output is correct
6 Correct 95 ms 39988 KB Output is correct
7 Correct 295 ms 41260 KB Output is correct
8 Correct 218 ms 41108 KB Output is correct
9 Correct 443 ms 42972 KB Output is correct
10 Correct 480 ms 42768 KB Output is correct
11 Correct 222 ms 41208 KB Output is correct
12 Correct 440 ms 43684 KB Output is correct
13 Correct 441 ms 42792 KB Output is correct
14 Correct 372 ms 43760 KB Output is correct
15 Correct 389 ms 42516 KB Output is correct
16 Correct 193 ms 40532 KB Output is correct
17 Correct 363 ms 43384 KB Output is correct
18 Correct 196 ms 41284 KB Output is correct
19 Correct 103 ms 39460 KB Output is correct
20 Correct 121 ms 39752 KB Output is correct
21 Correct 361 ms 42604 KB Output is correct
22 Correct 284 ms 41816 KB Output is correct
23 Correct 480 ms 43860 KB Output is correct
24 Correct 474 ms 44580 KB Output is correct
25 Correct 525 ms 49572 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 32932 KB Output is correct
2 Correct 68 ms 33048 KB Output is correct
3 Correct 472 ms 43984 KB Output is correct
4 Correct 462 ms 44256 KB Output is correct
5 Correct 527 ms 46020 KB Output is correct
6 Correct 480 ms 45496 KB Output is correct
7 Correct 508 ms 46060 KB Output is correct
8 Correct 565 ms 45956 KB Output is correct
9 Correct 177 ms 40824 KB Output is correct
10 Correct 153 ms 41344 KB Output is correct
11 Correct 142 ms 41340 KB Output is correct
12 Correct 454 ms 44608 KB Output is correct
13 Correct 485 ms 45756 KB Output is correct
14 Correct 547 ms 46044 KB Output is correct
15 Correct 536 ms 45900 KB Output is correct
16 Correct 324 ms 43428 KB Output is correct
17 Correct 426 ms 43688 KB Output is correct
18 Correct 367 ms 42832 KB Output is correct
19 Correct 464 ms 44172 KB Output is correct
20 Correct 292 ms 42368 KB Output is correct
21 Correct 556 ms 46724 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 33088 KB Output is correct
2 Correct 63 ms 33016 KB Output is correct
3 Correct 447 ms 43340 KB Output is correct
4 Correct 464 ms 43944 KB Output is correct
5 Correct 480 ms 44060 KB Output is correct
6 Correct 548 ms 46216 KB Output is correct
7 Correct 460 ms 43820 KB Output is correct
8 Correct 494 ms 44696 KB Output is correct
9 Correct 510 ms 44908 KB Output is correct
10 Correct 516 ms 46648 KB Output is correct
11 Correct 480 ms 45880 KB Output is correct
12 Correct 532 ms 46420 KB Output is correct
13 Correct 193 ms 41392 KB Output is correct
14 Correct 248 ms 42304 KB Output is correct
15 Correct 284 ms 42300 KB Output is correct
16 Correct 201 ms 42100 KB Output is correct
17 Correct 141 ms 41288 KB Output is correct
18 Correct 221 ms 42520 KB Output is correct
19 Correct 472 ms 45112 KB Output is correct
20 Correct 507 ms 45384 KB Output is correct
21 Correct 503 ms 46004 KB Output is correct
22 Correct 527 ms 45400 KB Output is correct
23 Correct 513 ms 46128 KB Output is correct
24 Correct 512 ms 45960 KB Output is correct
25 Correct 386 ms 44728 KB Output is correct
26 Correct 572 ms 46472 KB Output is correct
27 Correct 329 ms 42484 KB Output is correct
28 Correct 334 ms 43136 KB Output is correct
29 Correct 320 ms 42220 KB Output is correct
30 Correct 275 ms 41488 KB Output is correct
31 Correct 365 ms 42608 KB Output is correct
32 Correct 292 ms 42032 KB Output is correct
33 Correct 346 ms 42764 KB Output is correct
34 Correct 468 ms 44260 KB Output is correct
35 Correct 494 ms 44292 KB Output is correct
36 Correct 365 ms 42400 KB Output is correct
37 Correct 301 ms 42272 KB Output is correct
38 Correct 302 ms 42648 KB Output is correct
39 Correct 526 ms 46488 KB Output is correct
40 Correct 529 ms 47328 KB Output is correct
41 Correct 525 ms 46448 KB Output is correct
42 Correct 549 ms 46380 KB Output is correct